Binary Tree Zigzag Traversal
You have been given a Binary Tree of 'N' nodes, where the nodes have integer values. Your task is to print the zigzag traversal of the given tree.

Note:

In zigzag order, level 1 is printed from left to right fashion, level 2 is printed from right to left. and level 3 is printed from left to right again, and so on…..

For example:

For the given binary tree

The zigzag traversal is [1, 4, 3, 5, 2, 7, 6]

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the 'T' test cases follow. The first line of each test case 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 below image

1 3 8 5 2 7 -1 -1 -1 -1 -1 -1 -1

Explanation :

Level 1 : The root node of the tree is 1 Level 2 : Left child of 1 = 3 Right child of 1 = 8 Level 3 : Left child of 3 = 5 Right child of 3 = 2 Left child of 8 =7 Right child of 8 = null (-1) Level 4 : Left child of 5 = null (-1) Right child of 5 = null (-1) Left child of 2 = null (-1) Right child of 2 = null (-1) Left child of 7 = null (-1) Right child of 7 = null (-1) The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on. The input ends when all nodes at the last level are 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 3 8 5 2 7 -1 -1 -1 -1 -1 -1 -1

Output Format:

For each test case, print a single line containing all the nodes value in zigzag order traversal separated by a single space in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Binary Tree Zigzag Traversal

You have been given a Binary Tree of 'N' nodes, where the nodes have integer values. Your task is to print the zigzag traversal of the given tree.

Note:

In zigzag order, level 1 is printed from left to right fashion, level 2 is printed from right to left. and level 3 is printed from left to right again, and so on…..

For example:

For the given binary tree

The zigzag  traversal is [1, 4, 3, 5, 2, 7, 6]

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the 'T' test cases follow.

The first line of each test case 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 below image

1
3 8
5 2 7 -1
-1 -1 -1 -1 -1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 3
Right child of 1 = 8

Level 3 :
Left child of 3 = 5
Right child of 3 = 2
Left child of 8 =7
Right child of 8 =  null (-1)


Level 4 :
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 2 = null (-1)
Right child of 2 = null (-1)
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are 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 3 8 5 2 7 -1 -1 -1 -1 -1 -1 -1

Output Format:

For each test case, print a single line containing all the nodes value in zigzag order traversal separated by a single space in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= 'T' <= 100
0 <= 'N' <= 10^3
0 <= 'NODES' <= 10^9    

Where NODES represent any node value

Time Limit: 1sec

Accepted Answer

Brute force

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 - First level of tree should be printed in left to right manner, Second level of tree should be printed in right to 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.

We will first calculate the maximum level of the binary tree, then we will run a loop from 1 to maximum level and store nodes of each level in our answer based on direction.

If direction is 0 then traverse the whole binary tree from left to right and store nodes of current level in left to right fashion.

If direction is 1 then traverse the whole binary tree from right to left and store nodes of current level in right to left fashion.

Space Complexity: O(n)Explanation:

O(N), where N is the total number of nodes in the given binary tree.

In the worst case, when the tree is skewed an extra space of O(N) is required for recursion stack. Hence the overall complexity will be O(N).

Time Complexity: O(n^2)Explanation:

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

In the worst case,the tree can be skewed, then we will be going down for every level from the root which will result in a time complexity of order O(N^2).Hence the overall time complexity will be O(N^2).

Accepted Answer

Two stack approach

The idea here is to use two stacks, one to store odd levels and the other to store even level nodes. We will pop all nodes from the odd level stack and add children’s of a popped node from left to right to even level stack. Then we will pop all nodes from the even level stack and add their children from right to left in the odd level stack. As stack works last in fast out order so we will put children in reverse order so that we can get original order.

Steps :

Declare an empty array answer to store zigzag traversal.
Declare two empty stacks for odd level and even level.
Initially push root to an odd level stack.
Run a loop until both stacks are not empty and do:
1. Run a loop until the odd level stack is not empty and do:
  1. Pop the top node from it.
  2. Add data from popped node to the answer.
  3. Add a left child and right child of popped node to even level stack.
2. Run a loop until the even level stack is not empty and do:
  1. Pop the top node from it.
  2. Add data from popped node to the answer.
  3. Add the right child and left child of the popped node to an odd level stack.
At last return answer.

Space Complexity: O(n)Explanation:

O(N), where N is the total number of nodes in the given binary tree.

In the worst case, we are using a two stack which requires additional O(N) space. So the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where N is the total number of nodes in the given binary tree.

In the worst case, we are visiting each node exactly once. Hence the overall time complexity will be O(N).

Accepted Answer

Deque Approach

The idea here is to use a breadth-first search i.e. BFS along with deque.

We will run a BFS and if the level is odd then we will pop elements from front and children of a popped node from left to right in back of the deque.

If the level is even then we will pop all nodes from the back and then add children's popped node from right to left in front of deque.

Steps :

Declare an empty array answer to store zigzag traversal.
Declare an empty deque and push back root to it.
Declare a variable level to get current level and initialize it to 1.
Run a loop until deque is not empty and do:
1. Size of deque denotes the number of nodes in the current level.
2. Run a loop until total nodes in the current level are greater than zero, and do:
  1. If the level is odd then pop the front node from deque and add its data to answer.
  2. Push the left and right child of the popped node to deque.
  3. If the level is even then pop back node from deque and add its data to answer.
  4. Push the right and left child of the popped node to the front of the deque.
3. Increment level by 1.
Return the answer.

Space Complexity: O(n)Explanation:

O(N), where N is the total number of nodes in the given binary tree.

In the worst case, we are using a deque that requires additional O(N) space. So the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where N is the total number of nodes in the given binary tree.

In the worst case, we are visiting each node exactly once. Hence the overall time complexity will be O(N).

Accepted Answer

Queue Approach

The idea here is to use a breadth-first search i.e. BFS along with the queue.

We use an array to store nodes in current level if the level is even then we will add elements of the array in reverse order otherwise we will add elements of the array in the same order.

Steps :

Declare an empty array answer to store zigzag traversal.
Declare an empty queue and push root to it and declare a boolean variable reverseOrder which will tell us whether we should include nodes in current level in the original order or reverse order.
Initialize reverseOrder as false.
Run a loop until the queue is not empty and do:
1. Size of queue denoted by variable size i.e the number of nodes in the current level.
2. Create an array to store elements of the current level, say currentLevelNodes.
3. Run a loop until nodes in the current level are greater than zero and add all its nodes data to currentLevelNodes
4. Push left and right child of current level nodes to queue for next-level iteration
5. If reverseOrder is false then add elements of currentLevelNodes to answer, else add elements of currentLevelnodes to answer in reverse order.
6. Change reverseOrder to false if it is true and vice-versa for the next level.

5. At last, return the answer.

Space Complexity: O(n)Explanation:

O(N), where N is the total number of nodes in the given binary tree.

In the worst case, we are using a queue that requires additional O(N) space. So the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where N is the total number of nodes in the given binary tree.

In the worst case, we are visiting each node exactly once.Hence the overall time complexity will be O(N).

You have been given a Binary Tree of 'N' nodes, where the nodes have integer values. Your task is to print the zigzag traversal of the given tree.

Note:

For example:

Input Format:

Explanation :

Note :

Output Format:

Note :

Constraints:

Top PubMatic SDE-2 interview questions & answers

Popular interview questions of SDE-2