Spiral Order Traversal of a Binary Tree
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

Question

Spiral Order Traversal of a Binary Tree

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.

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

Accepted Answer

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’

Space Complexity: OtherExplanation:

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

Recursion space will be used.

Time Complexity: O(n^2)Explanation:

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)

Accepted Answer

Using Stack

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.

Space Complexity: O(n)Explanation:

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

Both stacks can hold at most all the ‘N’ nodes of the binary tree, hence the space complexity is linear.

Time Complexity: O(n)Explanation:

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

As all the ‘N’ nodes will be pushed and popped in one of the stacks exactly once, the time complexity will be linear.

You have been given a binary tree of 'N' nodes. Print the Spiral Order traversal of this binary tree.

For example

Input Format

Explanation

Note

Output Format:

Note

Constraints

Top Nagarro Technical Trainee interview questions & answers

Popular interview questions of Technical Trainee