import java.util.Stack;
class Node {
	public Node left;
	public int data;
	public Node right;

	public Node(int val) {
		this.data = val;
	}

	@Override
	public String toString() {
		return this.data + "";
	}
}
/**
 * Zig Zag Level Order Traversal ( 2 stacks used)
 * @author Prateek Rathore
 */
 class ZigZagTraversal {

	public void zigzagTraverse(Node root){

		if(root == null)
			return;

		Stack<Node> oddstack = new Stack<Node>();  //holds root as first element
		Stack<Node> evenstack = new Stack<Node>();

		oddstack.add(root);

		while(!oddstack.isEmpty() || !evenstack.isEmpty())
		{
			while(!oddstack.isEmpty())
			{
				Node item=oddstack.pop();
				System.out.print(item.data+"\t");
				
				if(item.left!=null)
					evenstack.push(item.left);
				
				if(item.right!=null)
					evenstack.push(item.right);
			}

			System.out.println();
			while(!evenstack.isEmpty())
			{
				Node item=evenstack.pop();
				System.out.print(item.data+"\t");

				if(item.right!=null)
					oddstack.push(item.right);
				
				if(item.left!=null)
					oddstack.push(item.left);
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		ZigZagTraversal obj = new ZigZagTraversal();

		Node root = new Node(1);
		root.left = new Node(2);
		root.left.left = new Node(4);
		root.left.right = new Node(5);
		root.left.right.left = new Node(8);
		root.left.right.right = new Node(9);
		root.left.right.left.left = new Node(10);

		root.right = new Node(3);
		root.right.left = new Node(6);
		root.right.right = new Node(7);

		System.out.println("Zig Zag Traversal is :");
		obj.zigzagTraverse(root);
	}
}