Bottom View of Binary Tree
Values visible from below: for each column, the last node in level order.
Open on GeeksforGeeks ↗02
Intuition
Same column trick as vertical order, but per column you keep only the deepest (and among equals, latest-visited) node. BFS makes 'latest = lowest' automatic: just overwrite the column entry on every visit.
03
Approach
1
BFS with column index
Queue carries (node, col). Left −1, right +1.
2
Overwrite per column
map[col] = node.val unconditionally — BFS visits top-down, so the final write per column is the bottom-most node.
3
Read columns in order
Output map values sorted by column key.
04
Solution & live demo
python
▶1from collections import deque
▶2
▶3def bottom_view(root):
▶4 if not root: return []
▶5 seen = {}
▶6 q = deque([(root, 0)])
▶7 while q:
▶8 node, c = q.popleft()
▶9 seen[c] = node.val # last write per column wins
▶10 if node.left: q.append((node.left, c - 1))
▶11 if node.right: q.append((node.right, c + 1))
▶12 return [seen[c] for c in sorted(seen)]
05
Edge cases
Two bottom nodes share a column
BFS order decides (the later one wins) — matching GFG's expected output.
Top view variant
Same code but write only if the column is unseen — first wins instead of last.
06
Complexity
Time
O(n log n)
Space
O(n)
BFS + sort of column keys.