Top View of Binary Tree | BFS with Horizontal Distance Mapping

The Top View of Binary Tree problem asks us to return the set of nodes visible when looking at the binary tree from above.

• Each node has a horizontal distance (HD) from the root:
  • Root → HD = 0
  • Left child → HD - 1
  • Right child → HD + 1
• For each HD, the first node encountered during level-order traversal (BFS) is part of the top view.

We must output the nodes from leftmost HD to rightmost HD.

Here’s the [Problem Link] to begin with.

Example

Example 1

Input: 
      1
     / \
    2   3
     \
      4
       \
        5
         \
          6

Output: [2, 1, 3, 6]
Explanation: From the top, nodes 2, 1, 3, and 6 are visible.

Example 2

Input:
       10
      /  \
     20   30
    /  \
   40  60

Output: [40, 20, 10, 30]

Intuition and Approach

The key idea is to track the horizontal distance (HD) of each node during traversal.

1. Start with the root at HD = 0.
2. Use BFS (level-order traversal) to ensure that the first node at each HD is captured.
3. Maintain a dictionary hd_map where:
   • Key = HD
   • Value = Node data
   • Only store the first occurrence of each HD.
4. Traverse the entire tree, updating left and right children with HD – 1 and HD + 1.
5. Sort keys of hd_map and return values in order.

This guarantees that we collect the correct top view.

Code Implementation

# Tree Node
# class Node:
#     def __init__(self, val):
#         self.right = None
#         self.data = val
#         self.left = None

from collections import deque

class Solution:
    def topView(self, root):
        if not root:
            return []
        
        # dictionary to store first node for each horizontal distance
        hd_map = {}
        
        # queue for BFS -> stores (node, horizontal_distance)
        q = deque([(root, 0)])
        
        while q:
            node, hd = q.popleft()
            
            # store the first node we encounter at this HD
            if hd not in hd_map:
                hd_map[hd] = node.data
            
            # add left and right children with updated HD
            if node.left:
                q.append((node.left, hd - 1))
            if node.right:
                q.append((node.right, hd + 1))
        
        # extract results sorted by horizontal distance
        result = [hd_map[key] for key in sorted(hd_map.keys())]
        return result

Code Explanation

• BFS Traversal:
  • Uses a queue to traverse the tree level by level.
• Horizontal Distance (HD):
  • Root = 0, left child = -1, right child = +1.
• hd_map:
  • Captures only the first node at each HD.
  • Ensures top-most node is chosen.
• Sorting:
  • Keys are sorted to print nodes from leftmost to rightmost.

Dry Run

Input Tree:

      1
     / \
    2   3
     \
      4
       \
        5
         \
          6

Step-by-step BFS traversal:

1. Start → (1, 0) → store hd_map[0] = 1.
2. Left → (2, -1) → store hd_map[-1] = 2.
3. Right → (3, +1) → store hd_map[1] = 3.
4. Next → (4, 0) → already exists, ignore.
5. Next → (5, 1) → already exists, ignore.
6. Next → (6, 2) → store hd_map[2] = 6.

Final hd_map = {-1:2, 0:1, 1:3, 2:6}

Sorted output = [2, 1, 3, 6]

Time and Space Complexity

• Time Complexity:
  • BFS traversal → O(N)
  • Sorting keys of hd_map → O(K log K), where K = number of unique HDs
  • Total → O(N log K)
• Space Complexity:
  • Dictionary for storing nodes → O(K)
  • Queue for BFS → O(N)
  • Total → O(N)

Conclusion

The Top View of Binary Tree problem is solved efficiently using BFS and horizontal distance mapping.

• Each node is assigned an HD.
• The first node encountered at each HD is chosen.
• Sorting ensures correct left-to-right order.

This method runs in O(N log K) time and O(N) space, making it optimal for large binary trees.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.