Spiral Order Traversal of a Binary Tree

Easy
0/40
Average time to solve is 20m
profile
Contributed by
16 upvotes
Asked in companies
SliceOYOMicrosoft

Problem statement

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
Detailed explanation ( Input/output format, Notes, Images )
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.

tree

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
Sample Input 1
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Sample Output 1:
1 3 2 4 5 6 7
Explanation of Sample Input 1:

tree

From the above-depicted representation of the input tree,

Level-0: 1(taken in the left to right fashion)
Level-1: 3 2(taken in the right to left fashion)
Level-2: 4 5 6(taken in the left to right fashion)
Level-3: 7(taken in the right to left fashion)

When taken all the sequences linearly from levels 0 to 3, we get [1, 3, 2, 4, 5, 6, 7] and hence the desired output.
Sample Input 2
1 2 3 -1 4 5 6 7 8 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 2
1 3 2 4 5 6 8 7
Hint

Use level order traversal to explore the binary tree in spiral order.

Approaches (2)
Level Order Traversal

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’
Time Complexity

O(N^2), where ‘N’ is the number of nodes in the binary tree.

In the case of skewed trees, we will be going down for every level from the root which will result in time complexity of order O(N^2)

Space Complexity

O(h), where 'h' is the height of the binary tree

 

Recursion space will be used.

Code Solution
(100% EXP penalty)
Spiral Order Traversal of a Binary Tree
Full screen
Console