Last Updated: 27 Jul, 2020
Top View
Moderate
Asked in companies
Given a binary tree. Print the Top View of Binary Tree. Print the nodes from left to right order.
Example:
Input:
Output: 2 35 2 10 2
Input format :
The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of input contains the elements of the tree in the level order form separated by a single space.
If any node does not have a left or right child, take -1 in its place. Refer to the example below.
Example:
Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 on its place.
For example, the input for the tree depicted in the below 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)
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 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format :
For each test case, print the Top View of Tree from left to right.
Output for every test case will be printed in a separate line.
Constraint :
1 <= T <= 100
1 <= N <= 1000
Time Limit : 1 sec
Approaches
Before looking at the approach, let's define a couple of terms; the level of a node and the distance of a node. The level of a node means the depth of the node with respect to the root node. So, the level of the root node will be 0, its children's would be 1, and so on. To generalize, if the level of a node is ‘x’, then the level of its children would be ‘x + 1’.
The distance of a node is a measure of how far a node is from the root node in the horizontal direction. It is negative in the left direction and positive in the right direction. For example, the distance for the root node is 0, the distance for root's left child is -1 and for its right child is 1. To generalize, if the distance of a node is ‘x’, then the distance for its left child would be ‘x - 1’ and for its right child would be ‘x + 1’.
The following image will give an example of a tree with the level and distance of all nodes marked in the format ('distance', ‘level’)
- We will be doing a depth-first search. An edge case would be when the root is null. in that case we will simply return without doing anything
- The main idea is that let’s say the root is at a distance 0 and if we go towards its right, child distance should be increased by 1 for the right child and distance should be decreased by 1 if we go towards the left child.
- It should be noted that if you see from the top you will be able to see only those nodes which come first at a distance from the root and others will get hidden by these. So we need to know the distance and level of a node from the root.
- To store distance and level of a node we will maintain a hashmap.
- Now start DFS from the root with its level 0 and distance 0 from the root. If the distance of this node from the root is not present in the hashmap simply add a pair of node value and level of this node at the present distance of the given node. Else if there is a node at a distance then we will be able to see which is at a lower level so compare the level of the current node and the node present at this distance from the hashmap. If the current node is at a lower level, update the hashmap at the current distance with current node value and it’s level.
- Now since we will be using an ordered-map or any tree-based map which keeps the key sorted so if we traverse the hashmap leftmost distance will come first so traverse the map and print the node value which is stored in the hashmap.
Before looking at the approach, let's define a couple of terms; the level of a node and the distance of a node. The level of a node means the depth of the node with respect to the root node. So, the level of the root node will be 0, its children's would be 1, and so on. To generalize, if the level of a node is ‘x’, then the level of its children would be ‘x + 1’.
The distance of a node is a measure of how far a node is from the root node in the horizontal direction. It is negative in the left direction and positive in the right direction. For example, the distance for the root node is 0, the distance for root's left child is -1 and for its right child is 1. To generalize, if the distance of a node is ‘x’, then the distance for its left child would be ‘x - 1’ and for its right child would be ‘x + 1’.
The following image will give an example of a tree with the level and distance of all nodes marked in the format ('distance', ‘level’)
- We will be doing a depth-first search. An edge case would be when the root is null. in that case we will simply return without doing anything
- The main idea is that let’s say the root is at a distance 0 and if we go towards its right, child distance should be increased by 1 for the right child and distance should be decreased by 1 if we go towards the left child.
- It should be noted that if you see from the top you will be able to see only those nodes which come first at a distance from the root and others will get hidden by these. So we need to know the distance and level of a node from the root.
- To store distance and level of a node we will maintain a hashmap.
- Now start DFS from the root with its level 0 and distance 0 from the root. If the distance of this node from the root is not present in the hashmap simply add a pair of node value and level of this node at the present distance of the given node. Else if there is a node at a distance then we will be able to see which is at a lower level so compare the level of the current node and the node present at this distance from the hashmap. If the current node is at a lower level, update the hashmap at the current distance with current node value and it’s level.
- Now since we will be using an unordered-map that doesn't keep the keys sorted, we'll need to figure out the minimum and maximum level that the tree stores so that if we traverse the hashmap from the minimum level to the maximum level, we'll get the correct order for the nodes.
- To get the minimum and maximum levels, just pass a reference to these two values in your function and update them whenever you make a new entry in your hashmap.