Spiral level order traversal of a binary tree

Given a binary tree, write a program to print nodes of the tree in a spiral order.

The idea to traverse the given binary tree in spiral order is similar to level order traversal.

In level order traversal we make use of a single queue while in spiral order traversal we need use two stacks. First stack('stackEven') is used to traverse the nodes at even level and second stack('stackOdd') is used to traverse the nodes at odd level. Nodes at even level are stored in 'stackEven' and are pushed in it from left to right order whereas nodes at odd level are stored in 'stackOdd' and are pushed in it from right to left order.

Algorithm:
1. Push root node into the 'stackEven'. Set boolean 'evenLevel' to true. This boolean variable is used to indicate if the current level being visited is even level or odd level.

2. Now if 'evenLevel' is set to true repeat steps 2a to 2c until 'stackEven' is not empty.
2a. Pop the node from 'stackEven'. Let popped node be 'currentNode'. Print the value of 'currentNode'.
2b. If the right child of 'currentNode' is not null, push it into the 'stackOdd'.
2c. If the left child of 'currentNode' is not null, push it into the 'stackOdd'.
Notice that currentNode's right child is pushed first and then its left child is pushed.

3. If 'evenLevel' is not set to true then repeat steps 3a to 3c until 'stackOdd' is not empty.
3a. Pop the node from 'stackOdd'. Let popped node be 'currentNode'. Print the value of 'currentNode'.
3b. If the left child of 'currentNode' is not null, push it into the 'stackEven'.
3c. If the right child of 'currentNode' is not null, push it into the 'stackEven'.
Notice that currentNode's left child is pushed first and then its right child is pushed.

4. If 'evenLevel' is true set it to false and if it is false set it to true. This is because the next level visited would be odd if current level is even and vice versa.


5. Repeat steps 2-4 until both 'stackEven' and 'stackOdd' are not empty.

The time complexity of this algorithm is O(n) and extra space used is also O(n). Please add comments below in case you have any queries/feedback.

Code and Algorithm Visualization:
http://www.ideserve.co.in/learn/spira...

Website: http://www.ideserve.co.in

Facebook:   / ideserve.co.in