Print/Traverse a Binary Tree in Zigzag Order

Posted by N.K. Chauhan on Mar 31, 2024

Given a binary tree, print it's elements in Zigzag Order, see the example below for illustration:

Example 1: Print a Binary Tree in Zigzag Order

Input:

Output: 1, 3, 2, 4, 5, 6, 7, 9, 8


Solutions

Method 1: Using two Stacks

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)

Complexity
The time complexity of this solution is O(n) and space complexity is O(n+n) due to auxiliary Stacks.

Method 2: Using Queue & List

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)

Complexity

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

Related


Print diagonal traversal of a binary tree

In-order Tree Traversal - Iterative and Recursive

Pre-order Tree Traversal - Iterative and Recursive

Find the diameter or width of a binary tree

Print the left view of a binary tree

Create a mirror tree from a given binary tree

Write a program to print height/depth of a Binary Tree

Level Order or Breadth First traversal of Binary Tree

Print a Binary Tree in Vertical Order

Print Nodes in Top View of a Binary Tree