Given a binary tree, return the zigzag level order traversal of its nodes' values.

For example: Given binary tree [3,9,20,null,null,15,7]

     5
   /  \
  3    20
       / \
      7   8
returns zig-zag order
[
  [3],
  [20,9],
  [15,7]
]

The problem can be solved using BFS traversal. Start traversing the tree and move elements in a stack level by level. For each level insert into a list and depending on the level, have a flag to insert from start or end of the list.

 public class Solution { 
 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
	List<List<Integer>> list = new ArrayList<List<Integer>>();
	if (root == null)
		return list;

	Queue<TreeNode> stack = new LinkedList();
	stack.add(root);
	int count = 1;
	boolean leftToRight = true;
	while (!stack.isEmpty()) {
		int futureCount = 0;
		LinkedList<Integer> l = new LinkedList<Integer>();
		while (count > 0) {
			TreeNode t = stack.poll();
			if (leftToRight) {
				l.add(t.val);
			} else {
				l.addFirst(t.val);
			}
			if (t.left != null) {
				stack.add(t.left);
				futureCount++;
			}
			if (t.right != null) {
				stack.add(t.right);
				futureCount++;
			}
			count--;
		}
		count = futureCount;
		list.add(l);
		leftToRight = !leftToRight;
	}
	return list;
}

static class TreeNode {
	TreeNode left;
	TreeNode right;
	int val;

	public TreeNode(int value) {
		this.val = value;
	}
}}