Print top view of a binary tree using level order traversal
Given a binary tree, print the values of nodes that would appear when the tree is viewed from top. Print the node values starting from left-most end. A node will be in the top-view if it is the topmost node at its horizontal distance from the root. Horizontal distance of root from itself is 0. Horizontal distance of right child of root node is 1 and horizontal distance of left child of root node is -1.
Horizontal distance of node 'n' from root = horizontal distance of its parent from root + 1, if node 'n' is right child of its parent Horizontal distance of node 'n' from root = horizontal distance of its parent from root - 1, if node 'n' is left child of its parent
If more than one nodes are at the same horizontal distance and are the topmost nodes for that horizontal distance, then you can choose to include either of the nodes in the top view.
example - For the following tree: 1 2 3 4 5 6 7
Horizontal distance of 1 = +0 Horizontal distance of 2 = -1 Horizontal distance of 3 = +1 Horizontal distance of 4 = -2 Horizontal distance of 5 = +0 Horizontal distance of 6 = +0 Horizontal distance of 7 = +2
and the top view would be 4, 2, 1, 3, 7.
Please note that though there are three nodes(nodes 1,5,6) with horizontal distance of 0, only node 1 is in top view because it is at the top-most level of all three nodes.
For the following tree:
1 2 3 4 5 6 7 8 9 10 11
Horizontal distance of 1 = +0 Horizontal distance of 2 = -1 Horizontal distance of 3 = +1 Horizontal distance of 4 = -2 Horizontal distance of 5 = +0 Horizontal distance of 6 = +0 Horizontal distance of 7 = +2 Horizontal distance of 8 = -1 (right child of 4) Horizontal distance of 9 = -1 (left child of 5) Horizontal distance of 10 = +1 (right child of 6) Horizontal distance of 11 = +3 (right child of 7)
and the top view would be 4, 2, 1, 3, 7, 11
Video coming soon!
Subscribe for more updates
Preparing for interviews? IDeserve team is here to help.
Create your profile
Create your profile, and here is what you will get:
1: Interview practice platform.
2: Once you are ready to take the interview, IDeserve team will help you get connected to the best job opportunities.
3: Personalized mentorship from IDeserve team once your interview process has started.
Creation of profile shouldn't take more than 2 minutes.
To solve this problem we use a simple idea of using level order traversal with slight modification. The modification is that while doing the level order traversal, we keep track of the horizontal distance(from the root node) of the current node being visited. During this level-order traversal, we update the treeMap(a modified hashMap which keeps entries sorted by key) with node's horizontal distance as key and value as current node's value if the node being visited is the topmost node seen at its horizontal distance. And because we are doing a level order traversal starting from topmost level, all we need to do is update the treeMap with (nodeValue, horizontalDistance) when the node being visited is the first node for its horizontal distance.
The algorithm is as following - 1. Initialize viewMap to a empty treeMap. 2. Call fillUpViewMap function with arguments as (root = root, viewMap = viewMap) 3. If root is null, do nothing and return. 4. If root is not null then - (following steps basically do a level order traversal of the given tree) 4a. Add the tuple(currentNode = rootNode, horizontalDistance = 0) to the queue - 'nodeQueue'. 4b. while 'nodeQueue' is not empty - remove first tuple(currentNode, horizontalDistance) from 'nodeQueue' - if viewMap does not contain an entry with 'horizontalDistance' as key, then that means this currentNode is the first and hence the topmost node at this 'horizontalDistance' and therefore, we update the viewMap with tuple(key = horizontalDistance, value = currentNode's value). If viewMap already contains an entry with 'horizontalDistance' as key, then we skip adding this node's value into the viewMap. - if left child of currentNode is not null, then we add tuple(currentNode.left, horizontalDistance - 1) to 'nodeQueue' - if right child of currentNode is not null, then we add tuple(currentNode.right, horizontalDistance + 1) to 'nodeQueue' 5. After completion of step #4, our viewMap is completely updated with keys(horizontal distance) and values(nodeValues) in sorted order of keys. All we need to do is print out the values in this viewMap to get the topView.
Please checkout code snippet and algorithm visualization section for more details of the algorithm.
Support us by whitelisting IDeserve in your ad-blocker.