Level Order Traversal in Zig Zag pattern OR Print in Spiral Pattern
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.
Better Solution :
- Idea is to take all nodes at each level and print them forward and reverse order alternatively.
- Create a 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 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 it 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)
Complete Code:
Output:
Spiral Print of a Tree : [5] [10, 15] [35, 30, 25, 20] [40, 45]