Level order traversal in spiral form
Solution:
- Take 2 stacks
- And consume from one stack and push children to another stack
- Most important part is, during pushing to stack push in alternate fashion, mean (if you are push left and then right child to stack1 and in stack2 push first right child and then left child)
Algorithm:
- Create two stack S1 and S2
- Push tree root to S1
- Iterate till S1 and S1 not empty
- Iterate till S1 is not empty
- Node = S1.pop
- Print Node
- If node has right child then
- push right child to S2
- If node has left child then
- push left child to S2
- Iterate till S2 is not empty
- Node = S2.pop
- Print Node
- If node has left child then
- push left child to S1
- If node has right child then
- push right child to S2
- Iterate till S1 is not empty
Latest Source Code:
Github: BinaryTreeLevelOrderTraversalInSpiralForm.java
Output:
50 / \ / \ 30 70 / \ / \ 20 40 60 80 Printing in spiral form : 50 30 70 80 60 40 20