Top view of a binary tree  Part1
Introduction
Let's begin with understanding the task first. Suppose there is a programming problem that asks you to print the top view of a binary tree. For example, consider the following binary tree
Now, if you print the top view of a binary tree, you will get the following output
8 4 2 1 3 7 
So, we can say that, in simplest words, the top view of a binary tree refers to the set of the nodes visible if we view the tree from an axis parallel to the levels of the tree. Or if we take the topmost nodes of all the vertical orders in it. Vertical orders refer to the set of nodes at a particular horizontal distance.
Though there are various methods to print the top view of a binary tree, we will start with discussing the basic method, which does the level order traversal of the binary tree and prints all the topmost nodes for each value of the horizontal distance. Then move on to advanced methods like twovariable methods etc.
The basic approach
This method does find vertical orders in the tree with the help of the horizontal distance of each node, the horizontal distance of the left child of a node is one less than the parent, and the right child is one more than the parent.
Now we do the level order traversal of the tree to ensure that nodes appear in the top to bottom order for every vertical order, and we maintain a hashmap to keep track of the visited nodes for each vertical order.
Algorithm for basic approach
 Create a binary tree or take it from user input.
 Create a queue to hold nodes during the level order traversal of the tree.
 Create a map to keep track of the visited nodes.
 Start the level order traversal of the binary tree by pushing the root and its horizontal distance into the queue.
 Now run a loop while the queue is not empty
 Check if the map has a node at that horizontal distance; if no, push it in the map.
 Push the left and right child of the node in the queue, and update the value of their horizontal distance.
 Pop the element from the queue.
 Repeat step 5 with the front of the queue.
 Then print the values in the map.
Implementation of the basic approach

Output
8 4 2 1 3 7 
The time complexity of this approach is O(N*logN), an insertion in a map takes O(logN) time, and we had N nodes to process.
The time complexity of this approach is O(N).
The levelbased approach
In this approach, we also keep track of the level of the nodes along with their horizontal distance from the root. If we find a node with the same horizontal distance, then we check for its level. If the new node has a lower level, we replace it.
Algorithm for the levelbased approach
 Create a binary tree or take it from user input.
 Create a map that stores the horizontal distance of the nodes and a pair of nodes and their level as keyvalue pairs.
 Then we use a function to push the node into the map along its horizontal distance and level.
 Now the Function in step three does check if the map contains any value for the horizontal distance of the current node; if yes, compares both nodes and keeps the one with a lower level., or in case this is the first node corresponding to this horizontal distance it gets pushed into the map.
 We recursively call the Function in step 3 for the left and right child of the current node with updated horizontal distance and level values.
 Then we print the values stored in the map.
Implementation of the levelbased approach

Output
8 4 2 1 3 7 
The time complexity of this approach is O(N*logN), an insertion in a map takes O(logN) time, and we had N nodes to process.
The time complexity of this approach is O(N).
Frequently Asked Questions
 What is the top view of a binary tree?
The top view of a binary tree is the set of nodes that will be visible if we look at the binary tree from the top.
 How do you find the top view of a binary tree?
We can find the top view using the methods described in the blog, which mainly involves the level order traversal of the binary tree, and then we pick the nodes on the top of their vertical order.
 What is the top of a binary tree called?
The top of a binary tree is called the root node.
 What is a treetop view?
A treetop view refers to the set of the tree elements visible to use if we look at a tree from an axis parallel to the levels in it and above the tree's root node.
 What is the width of a binary tree?
The width of the binary tree is the level with the most number of nodes in it.
Key takeaways
In this blog, we have discussed the methods we can use to print the top view of a binary tree
 The first method is based on the level order traversal of the binary tree. We also use a hashmap to keep track of the visited node for each vertical order in the tree during the level order traversal. And any nodes that appear for the first time for their horizontal distance during the level order traversal will be included in the top view of a binary tree.
 The second method is the levelbased approach. In it, we find the level of the node along with its horizontal distance, and for every vertical order, pick the node with the lowest level. This method uses a map with horizontal distance and a pair of nodes and its level as keyvalue pairs.
You must check out the next part of this blog to know about more advanced methods on the top view of a binary tree. You can practice similar problems on CodeStudio as well.
Comments
No comments yet
Be the first to share what you think