Bottom View of Binary Tree | BFS with Horizontal Distance Mapping

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

• 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 last node encountered during level-order traversal (BFS) is part of the bottom view.

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

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

Example

Example 1

Input: 
      20
     /  \
    8   22
   / \     \
  5   3     25
     / \
    10  14

Output: [5, 10, 3, 14, 25]
Explanation: 
From the bottom, nodes 5, 10, 3, 14, and 25 are visible.

Example 2

Input:
       1
      / \
     2   3
    /
   4

Output: [4, 2, 3]

Intuition and Approach

The key idea is similar to Top View, but instead of taking the first node at each HD, we take the last node seen during BFS traversal.

Step-by-step approach:

1. Start with the root at HD = 0.
2. Perform BFS (level-order traversal).
3. For every node visited, update hd_map[hd] = node.data.
   • This way, the last node seen at each HD will overwrite previous ones.
4. After traversal, sort the keys of hd_map and return the values.

This ensures the bottom-most nodes are captured.

Code Implementation

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

from collections import deque

class Solution:
    def bottomView(self, root):
        if not root:
            return []
        
        # dictionary to store last node for each horizontal distance
        hd_map = {}
        
        # queue for BFS -> stores (node, horizontal_distance)
        q = deque([(root, 0)])
        
        while q:
            node, hd = q.popleft()
    
            # overwrite with the last node seen at this HD
            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 process nodes level by level.
• Horizontal Distance (HD):
  • Root = 0, left child = -1, right child = +1.
• hd_map:
  • Unlike Top View, we overwrite values for each HD to ensure we capture the bottom-most node.
• Sorting:
  • Keys are sorted to ensure left-to-right order of the bottom view.

Dry Run

Input Tree:

      20
     /  \
    8   22
   / \     \
  5   3     25
     / \
    10  14

Step-by-step BFS traversal:

1. Root (20, HD=0) → hd_map = {0: 20}
2. Left (8, HD=-1) → hd_map = {-1: 8, 0: 20}
3. Right (22, HD=1) → hd_map = {-1: 8, 0: 20, 1: 22}
4. Left child (5, HD=-2) → hd_map = {-2: 5, -1: 8, 0: 20, 1: 22}
5. Right child (3, HD=0) → overwrite → hd_map = {-2: 5, -1: 8, 0: 3, 1: 22}
6. Left (10, HD=-1) → overwrite → hd_map = {-2: 5, -1: 10, 0: 3, 1: 22}
7. Right (14, HD=1) → overwrite → hd_map = {-2: 5, -1: 10, 0: 3, 1: 14}
8. Right (25, HD=2) → hd_map = {-2: 5, -1: 10, 0: 3, 1: 14, 2: 25}

Final sorted output: [5, 10, 3, 14, 25]

Time and Space Complexity

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

Conclusion

The Bottom View of Binary Tree problem is efficiently solved using BFS with horizontal distance mapping.

• Unlike Top View, we overwrite entries at each HD to capture the bottom-most node.
• Sorting ensures the correct left-to-right order of nodes.
• Runs in O(N log K) time and O(N) space.

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