Last Updated: 20 Dec, 2020

Vertical Binary Tree

Easy

Asked in companies

Solve now

Problem statement

You are given an arbitrary binary tree consisting of N nodes numbered from 1 to N, your task is to print the nodes of this tree in the vertical order.

altImage

V1, V2, V3, V4 and V5 in the above figure denotes the vertical levels of the given binary tree. Now, if we want to print the tree in the vertical order, then we will start printing the node values on the segment V1 and will continue the same procedure till the segment V5, and while printing the node values for any vertical level, we will check if there is any node to the left of the current level which does not lie on any of the line segment then we will include that node also in the current level. For instance node with value 7 can be included in the level V3, and the node with value 8 can be included in the level V4.

The vertical traversal for the above binary tree would be 6 4 2 7 8 3 9.

Note:

1) The root node will be fixed and will be provided in the function.
2) Two nodes in the tree can have the same values, all values in the tree will be positive.
3) While printing the nodes for any particular vertical level print them in sorted order, i.e. in the above example nodes in the level 3 are 2,7 and 8 so it will be printed as 2 7 8.

Input Format:

The first line of the input contains a single integer T, representing the number of test cases.

The first line of each test case contains a single integer N denoting the number of nodes in the tree. 

The second line contains the values of the nodes of the tree in the level order form ( -1 for NULL node) Refer to the example for further clarification.

Example: Consider the binary tree

altImage

The input of the tree depicted in the image above will be like:

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)

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).

Output Format:

For each test case, print X space-separated integers, denoting the node values in the order as described in the problem statement.

Note:

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

Constraints:

1 <= T <= 100
1 <= N <= 10^4
1 <= nodeVal <= 10^9
Time Limit: 1sec

Solve now

Approaches

01 Approach

The fact that we need to find the vertical level order clearly indicates the need to do a level order traversal of the given tree. So we will run a BFS using a FIFO queue, but here it requires some modification because here we need to do the traversal in vertical order and we have to traverse each vertical level in a top-down fashion.
So, here we maintain a queue of pairs where the first element of the pair represents the node value and the second element of the pair contains its vertical level. Also, we will maintain a hashmap to store the nodes at each vertical level.
In the beginning, we will push the root and its level as 0 in the queue.
Now, we run a loop until the queue is not empty:
- Every time when we will pop a node from the queue we will insert that node in the hash map with key same as the level of the node popped.
- Now, we will push the left child and the right child of this node into the queue, and for their level, we can calculate it as, the level of left node = level of root-1 and the level of right node = level of root node +1.
After coming out of the loop iterate through the hashmap from left to right and print all the values in order as stored at any index of the hashmap.
Let us consider an example to understand the working of the algorithm. Consider the tree {1,2,3,-1,-1,-1,-1}:
- At the start, we will push the pair {1,0} into the queue, where 1 represents the node value and 0 represents the level.
- Now, we run a loop until the queue is not empty:
  - In the first go, we pop the pair {1,0} from the queue and now we insert 1 in the hashmap with key 0.
  - After that, we push {2,0-1=-1} and {3,0+1=1} into the queue.
  - Now, we pop {2,-1} from the queue and add 2 in the hashmap with key -1, and since it has no child so no new node will be pushed into the queue.
  - Similarly, when we will pop {3,1}, 3 will be inserted into the hashmap with key 1, and since this also doesn’t have any child so again there will be no new insertion.
- Finally, we will come out of the loop and iterate through the hashmap to retrieve the answer. So, starting from left to right we will get {2,1,3} as the answer because 2 is stored at key -1, then 1 is stored at key 0, and 3 is stored at key 1.

Solve now