CareerCup

private static void zigZagTraversal(BinaryTreeNode root) {
		int leftToRight=1;
		BinaryTreeNode temp;
		Stack<BinaryTreeNode> currentLevel=new Stack<BinaryTreeNode>();
		Stack<BinaryTreeNode> nextLevel=new Stack<BinaryTreeNode>();
		
		System.out.println("Zig Zag Traversal");
		currentLevel.push(root);
		while (!currentLevel.isEmpty()) {
			temp = currentLevel.pop();
			if(temp!=null)
			{
				System.out.println(temp.getData());
				if(leftToRight==1)
				{
					if (temp.getLeft() != null)
						nextLevel.push(temp.getLeft());
					if (temp.getRight() != null)
						nextLevel.push(temp.getRight());
				}
				else
				{
					if (temp.getRight() != null)
						nextLevel.push(temp.getRight());
					if (temp.getLeft() != null)
						nextLevel.push(temp.getLeft());
				}
				
			}
			if(currentLevel.isEmpty())
			{
				leftToRight=1-leftToRight;
				while(!nextLevel.isEmpty())
				{
					currentLevel.push(nextLevel.pop());
				}
			}
			
			
		}
	}

Convert the tree to an array representation. Then print the array.

// start with a list that contains only the root node
    private static void printRecursive(List<TreeNode> nodes, int direction) {
   
    	if (nodes.isEmpty()) return;
    	
    	List<TreeNode> successors = new LinkedList<>();
    	
    	for (int i = 0; i < nodes.size(); i++) {
    		System.out.println(direction == 1 ? nodes.get(i).value :
    				nodes.get(nodes.size() - i - 1).value);
    		
    		TreeNode node = nodes.get(i);
    		if (node.left != null) successors.add(node.left);
    		if (node.right != null) successors.add(node.right);
    	}
    	
    	printRecursive(successors, direction * -1); // change direction = zig zag
    }

// start with a list that contains only the root node
    private static void printRecursive(List<TreeNode> nodes, int direction) {
   
    	if (nodes.isEmpty()) return;
    	
    	List<TreeNode> successors = new LinkedList<>();
    	
    	for (int i = 0; i < nodes.size(); i++) {
    		System.out.println(direction == 1 ? nodes.get(i).value :
    				nodes.get(nodes.size() - i - 1).value);
    		
    		TreeNode node = nodes.get(i);
    		if (node.left != null) successors.add(node.left);
    		if (node.right != null) successors.add(node.right);
    	}
    	
    	printRecursive(successors, direction * -1); // change direction = zig zag
    }

// start with a list that contains only the root node
    private static void printRecursive(List<TreeNode> nodes, int direction) {
   
    	if (nodes.isEmpty()) return;
    	
    	List<TreeNode> successors = new LinkedList<>();
    	
    	for (int i = 0; i < nodes.size(); i++) {
    		System.out.println(direction == 1 ? nodes.get(i).value :
    				nodes.get(nodes.size() - i - 1).value);
    		
    		TreeNode node = nodes.get(i);
    		if (node.left != null) successors.add(node.left);
    		if (node.right != null) successors.add(node.right);
    	}
    	
    	printRecursive(successors, direction * -1); // change direction = zig zag
    }

Use to stacks and print them interchangeably.

public static void zigzag(BinaryTreeNode node) {
	
	Stack<BinaryTreeNode> currentStack = new Stack<BinaryTreeNode>();
	Stack<BinaryTreeNode> nextStack = new Stack<BinaryTreeNode>();
	currentStack.add(node);
	zigzag(currentStack, nextStack, true);
}

private static void zigzag(Stack<BinaryTreeNode> currentStack, Stack<BinaryTreeNode> nextStack, boolean reverse) {
	
	while (!currentStack.isEmpty()) {
		BinaryTreeNode pop = currentStack.pop();
		System.out.println(pop);
		if (reverse) {
			if (pop.left != null)
				nextStack.push(pop.left);
			if (pop.right != null)
				nextStack.push(pop.right);
		} else {
			if (pop.right != null)
				nextStack.push(pop.right);
			if (pop.left != null)
				nextStack.push(pop.left);
		}
		zigzag(nextStack, currentStack, !reverse);
	}
}