/*
// A Binary Tree node
class Node
{
    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }
}
*/

class GfG
{
      void printSpiral(Node node) 
      {
           // Your code here
           Stack<Node> lrst=new Stack<Node>();
           Stack<Node> rlst=new Stack<Node>();
           Node curr;
           if(node!=null)rlst.push(node);
           while(!rlst.empty() || !lrst.empty()){
               while(!rlst.empty()){
                   curr=rlst.pop();
                   System.out.print(curr.data+" ");
                   if(curr.right!=null)lrst.push(curr.right);
                   if(curr.left!=null)lrst.push(curr.left);
               }
               while(!lrst.empty()){
                   curr=lrst.pop();
                   System.out.print(curr.data+" ");
                   if(curr.left!=null)rlst.push(curr.left);
                   if(curr.right!=null)rlst.push(curr.right);
               }
           }
      }
}
