This post is completed by 1 user

  • 0
Add to List

51. Print Binary Tree Nodes in Zigzag Order: Spiral Traversal Pattern

Objective: Given a binary Tree, Do Level Order Traversal in a Zig Zag pattern OR Print in a Spiral

Level Order Traversal in Zig Zag pattern OR Print in Spiral

Better Solution :

  • The idea is to take all nodes at each level and print them forward and reverse order alternatively.
  • Create an ArrayList al.
  • Do the level order traversal using the queue(Breadth First Search). Click here to know about how to level order traversal.
  • For getting all the nodes at each level, before you take out a node from the queue, store the size of the queue in a variable, say you call it levelNodes.
  • Now while levelNodes>0, take out the nodes and add them to the array list and add their children into the queue.
  • Alternatively, print the array list in forward and backward order.
  • After this while loop put a line break.

Time Complexity: O(N)

Spiral Print of a Tree :
[10, 15]
[35, 30, 25, 20]
[40, 45]