Top View of Binary Tree

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?
• What is Top View in a Binary Tree?
• How to Calculate the Top View of a Binary Tree?
• 1. Using DFS
• 2. Using BFS
• Optimized Approach Using BFS
• Comparison Table of the Above Approaches
• Conclusion

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

Explore Program

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

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.

Step 3: Perform Traversal

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.

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.

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