Level Order Traversal in Zig Zag pattern OR Print in Spiral Pattern

by

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

Input: A Binary Tree

Output: Order Traversal in Zig Zag pattern OR Print in Spiral.

Level Order Traversal in Zig Zag pattern OR Print in Spiral
Level Order Traversal in Zig Zag pattern OR Print in Spiral


Better Solution :

  • 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 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 as 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)

Code:

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

Related Posts: