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:Run This Code

Output:

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