The top view of a binary tree represents the set of nodes visible when the tree is viewed from above, i.e., from the root of the tree. Imagine standing directly above the root of the tree; only the topmost nodes at each horizontal distance from the root are visible. This is a common and frequently asked problem in technical interviews and is solved by two primary approaches, DFS and BFS. In this article, we will learn about the top view of the binary tree with an example and its solution.
Table of Contents:
What is a Binary Tree?
A binary tree is a special type of data structure where:
- Each node can have at most two children.
- These two children are commonly referred to as the left child and the right child.
Each node in a binary tree usually has,
- Data is the value stored in the Node
- Left is a pointer to the left child
- Right is a pointer to the right child.
Example:
10
/
5 20
In the above example,
- 10 is the root node
- 5 is the left child of 10
- 20 is the right child of 10
- 5 and 20 are siblings, having a parent as 10.
For example, you can think of a family tree
- One person can have up to two children.
- You start from a grandparent, and for each person below, i.e., your father, can also have two children (you and your sibling).
Master DSA Today - Accelerate Your Future
Enroll Now and Transform Your Future
What is Top View in a Binary Tree?
The top view of a binary tree is the set of nodes when the tree is seen from the top. Each node in a binary tree has a horizontal distance (HD) and a level (depth) from the root.
The horizontal distance is the position of the binary tree with respect to the root node. It is calculated by
- The root node is always assigned a horizontal distance of 0.
- The left child of any node is assigned an HD of the parent’s HD − 1.
- The right child of any node is assigned an HD of the parent’s HD + 1.
The level (or depth) of a node represents how far the node is from the root in terms of vertical distance (i.e., how many edges you have to go down). It is calculated as follows:
- The root node is always at level 0.
- The left or right child of any node is at the parent’s level + 1.
- As you move down the tree, the level increases by 1 for each step from parent to child.
For example, consider the following tree
1
/
2 3
/ /
4 5 6
The top view of the above tree is 4, 2, 1, 3.
How to Calculate the Top View of a Binary Tree?
Our main goal is to print the top view of a binary tree. We will do this step by step using the example tree shown below.
1
/
2 3
/ /
4 5 6
Step 1: Assign Horizontal Distance (HD) and Level
For the above tree, the HD of each node is below,
- Root node is 1, having HD as 0
- Node 2 is the left child of the root node, hence it has the HD as -1
- Node 3 is the right child of the root node, hence it has the HD as +1
- Node 4 is the left child of Node 2, hence it has the HD as -2
- Node 5 is the right child of Node 2, hence it has the HD as 0
- Node 6 is the left child of Node 3, hence it has the HD as 0
Now, let us calculate the level of the above tree, as shown below:
- Root node is 1, hence it is at Level 0
- Node 2 is the left child of the root node, hence it is at Level 1
- Node 3 is the right child of the root node, hence it is at Level 1
- Node 4 is the left child of Node 2, hence it is at Level 2
- Node 5 is the right child of Node 2, hence it is at Level 2
- Node 6 is the left child of Node 3, hence it is at Level 2
Node |
HD |
Level |
1 |
0 |
0 |
2 |
-1 |
1 |
3 |
+1 |
1 |
4 |
-2 |
2 |
5 |
0 |
2 |
6 |
0 |
2 |
Step 2: Maintain a Map
Use a map structure as below to store the value, HD, value, and level of the binary tree.
Map<Integer, Pair<NodeData, Level>>
- The key is the horizontal distance (HD) from the root
- The map value is a pair of node data and its level.
The above map helps you ensure that only the topmost node is stored per HD.
You can perform the tree traversal by using DFS or BFS.
1. For BFS
Use a queue data structure to store the node, HD, and level. For each node,
- If HD is not in the map, or current level < stored level:
- Update map[HD] = (node.data, level)
- Enqueue left and right children with updated HD and level
2. For DFS
Use a preorder or inorder traversal to traverse using DFS.
- Pass (node, HD, level)
- If HD is not in the map, or level < stored level:
- Update map[HD] = (node.data, level)
- Recursively call for:
- Left: HD – 1, Level + 1
- Right: HD + 1, Level + 1
Step 4: Print Top View
Now, print the top view of the tree by sorting the map keys (HDs) from leftmost to rightmost (smallest to largest HD)
Now, let us understand it with the help of programs.
Print Nodes in Top View of Binary Tree
You can print the nodes of the top view of the binary tree by using the following approaches.
1. Using DFS
DFS (Depth First Search) is a tree traversal technique that explores all the nodes of a tree before backtracking starts. It starts from the root node and explores each child before moving to its siblings.
Example:
Output:
Explanation: In the above program dfs() function recursively traverses the tree and then changes the value of the map only if no node is present at that HD or if the current node is present at a higher level. The printTopView() function initiates the DFS traversal and prints the top view from leftmost to rightmost horizontal distance.
Get 100% Hike!
Master Most in Demand Skills Now!
2. Using BFS
BFS (Breadth-First Search) is a tree traversal technique that starts from a root node and explores a graph level by level by visiting all the neighbors of the current level of the node, before moving to another level.
Example:
Output:
Explanation: The above program defines a binary tree and prints its top view using a BFS and uses a SortedDict to keep track of the nodes that are horizontally sorted by distance (hd) from the root. A helper Pair class is used with each node to store its horizontal distance. The algorithm uses a queue and inserts the value into the map only if that horizontal distance comes for the first time.
Optimized Approach Using BFS
In this technique, the level-order traversal is performed by storing the first node at each horizontal level to maintain the order for the final output. It tracks the minimum and maximum horizontal distances at each traversal. Once the traversal is completed, the top view is constructed by iterating from the minimum to the maximum HD, and then printing the values from the dictionary.
Example:
Output:
Explanation: The above program uses a SortedDict (used as a level map) to maintain the first node that comes at each horizontal distance (hd) in sorted order. Each node is wrapped in a Pair class along with its hd, and inserted into a queue for level-order traversal. During traversal, if a horizontal distance has not been added to the map, the node’s value is stored. This ensures that only the topmost node at each HD is stored. After the BFS traversal completes, the values in the SortedDict are printed from leftmost to rightmost.
Comparison Table of the Above Approaches
Below is the comparison of the above approaches we have discussed so far.
Feature |
BFS |
DFS |
Optimized BFS |
Time Complexity |
O(n) |
O(n log n) |
O(n) |
Space Complexity |
O(n) |
O(n) |
O(n) |
Data Structures Used |
Queue and HashMap |
HashMap and Recursion |
Queue, HashMap, and LevelMap |
Code Complexity |
Medium |
High |
Medium to High |
Conclusion
From the above article, we learned that the top view of the Binary tree can be obtained by using mainly two approaches, i.e., BFS and DFS. BFS explores the tree level-wise, while DFS explores it depth-wise, but it is complex. Also, the BFS algorithm can be optimised by using a dictionary. For simplicity, DFS is better, and for optimized performance, BFS is perfect. The approach depends on the user’s preference and the use case.
If you want to learn more about the Binary Tree in detail, you can refer to our DSA Course.
Top View of Binary Tree – FAQs
Q1. What is a binary tree, and why is it important?
A binary tree is a structure where each node has at most two children. It helps organize data efficiently for searching, sorting, and hierarchical tasks.
Q2. What is the difference between top view and level order traversal?
The top view shows only the first visible node at each horizontal level, while level order shows all nodes level by level.
Q3. What are the key properties of a binary search tree?
The main key property of the binary search tree is that the left child < parent < right child, i.e., all left nodes are smaller, and right nodes are larger.
Q4. How can I print a binary tree structure?
Use level order traversal (BFS) or recursive printing with indentation for visual structure.
Q5. What does top view mean in trees?
It’s the set of nodes visible when the tree is viewed from the top.
Q6. Can a top view be generated using recursion?
Yes, using DFS with horizontal distance tracking.