Last Updated: 1 Aug, 2020
Spiral Order Traversal of a Binary Tree
Easy
Asked in companies
You have been given a binary tree of 'N' nodes. Print the Spiral Order traversal of this binary tree.
For example
For the given binary tree [1, 2, 3, -1, -1, 4, 5, -1, -1, -1, -1]
1
/ \
2 3
/ \
4 5
Output: 1 3 2 4 5
Input Format
The only line of input contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.
For example, the input for the tree depicted in the above image would be :
1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1
Explanation
Level 1 :
The root node of the tree is 1
Level 2 :
Left child of 1 = 2
Right child of 1 = 3
Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6
Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)
Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)
Note
The above format was just to provide clarity on how the input is formed for a given tree.
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format:
Print 'N' single space-separated integers representing the spiral order traversal of the binary tree.
Note
You do not need to print anything, it has already been taken care of. Just implement the given function and return the list of elements containing the spiral order of the given input tree.
Constraints
0 <= N <= 10 ^ 4
Where 'N' is the total number of nodes in the binary tree
Time Limit: 1 sec
Approaches
We can use level order traversal (recursive) to explore all levels of the tree. Also, at each level nodes should be printed in alternating order.
For example - The first level of the tree should be printed in left to the right manner, the Second level of the tree should be printed in right to the left manner, Third again in left to right order and so on
So, we will use a Direction variable whose value will toggle at each level and we will print levels in alternating order by looking at the direction of current level.
Algorithm
- Initialize an array ‘spiral’ to store the result.
- Initialize a variable ‘direction’ to keep track of traversing direction with 1(denoting left to right)
- Find the height of the given tree and store it in a variable ‘height’.
- Run a loop - level : 1 to height, to traverse through every level.
- Find level order traversal in the current direction.and store in ‘spiral’
- Toggle the direction.
- Return ‘spiral’
We can use a Stack Data Structure to solve this problem. A Stack follows First in, Last out strategy which is exactly the same as reversing.
Algorithm
- We will maintain two stacks, one for each direction i.e. leftToRight and rightToleft.
- We will do a level order traversal of the given binary tree and push nodes of each level onto one of the stack according to the current direction of traversal.
- After we’ve pushed all nodes of a level onto one stack, we’ll start popping those nodes. While popping the nodes we will push their children (if any) onto our other direction stack, so that the next level be traversed in reverse order.