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
- Root →
- 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:
- Start with the root at
HD = 0
. - Perform BFS (level-order traversal).
- For every node visited, update
hd_map[hd] = node.data
.- This way, the last node seen at each HD will overwrite previous ones.
- 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
.
- Root =
- 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:
- Root (20, HD=0) → hd_map = {0: 20}
- Left (8, HD=-1) → hd_map = {-1: 8, 0: 20}
- Right (22, HD=1) → hd_map = {-1: 8, 0: 20, 1: 22}
- Left child (5, HD=-2) → hd_map = {-2: 5, -1: 8, 0: 20, 1: 22}
- Right child (3, HD=0) → overwrite → hd_map = {-2: 5, -1: 8, 0: 3, 1: 22}
- Left (10, HD=-1) → overwrite → hd_map = {-2: 5, -1: 10, 0: 3, 1: 22}
- Right (14, HD=1) → overwrite → hd_map = {-2: 5, -1: 10, 0: 3, 1: 14}
- 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.