Print/Traverse a Binary Tree in Zigzag Order

Observing closely we can find that, to print a binary tree in "ZigZag" order we need to print "even levels" of the tree from "left-to-right" and "odd levels" from "right to left".

We can achieve this using "two stacks", one to hold even level nodes and other to hold odd level nodes.

Add root to even-stack, keep the loop going until both stacks are not empty.

The idea is to pop elements from one stack one-by-one and print, also store their children in other stack - "right than left" for odd-stack and "left than right" for even-stack.

if(root==null)
   return;
evenLevel -> empty stack
evenLevel.add(root)
oddLevel -> empty stack
while(not empty evenLevel || not empty oddLevel)
   while(not empty evenLevel)
      node -> evenLevel.pop()
      print(node)
      if (node.left != null)
          oddLevel.add(node.left)
      if (node.right != null)
          oddLevel.add(node.right)
   while (not empty oddLevel)
      node = oddLevel.pop()
      print(node.data + ", ")
      if (node.right != null)
         evenLevel.add(node.right)
      if (node.left != null)
         evenLevel.add(node.left)

Observing closely we can find that, to print a binary tree in "ZigZag" order we need to print "even levels" of the tree from "left-to-rigt" and "odd levels" from "right to left".

We can achieve this with the help of a "temporary list" while traversing the tree level-by-level using Queue.

The "tmp list" will be used to "store, reverse (if needed) and print" nodes of one level at a time, the remaining level order traversal algorithm using queue has no change.

The idea is to "add and print" nodes for even levels while "add, reverse list and print" nodes for odd levels.

if (root == null)
  return
q -> empty queue
q.add(root)
evenLevel -> true
while (!q.isEmpty())
  int size = q.size();
  nodesFromOneLevel -> empty list
  for (int i = 0; i < size; i++)
    n -> q.poll()
    nodesFromOneLevel.add(n);
    if (n.left != null)
      q.add(n.left)
    if (n.right != null)
      q.add(n.right)
  if (evenLevel) 
    evenLevel -> false
  else 
    reverse(nodesFromOneLevel)
    evenLevel = true
  forEach(i->nodesFromOneLevel)
  	print(i.data)

The time complexity of this solution is O(n) and space complexity is O(2n) or O(n) due to auxiliary Queue & List.