Bottom View of Binary Tree
Values visible from below: for each column, the last node in level order.
Open on GeeksforGeeks ↗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.
Same column indexing as top view, opposite rule: top view keeps the first node seen per column, bottom view keeps the last. With BFS, later writes are automatically lower in the tree, so an unconditional overwrite gives the bottom view for free.
Approach
BFS with column index
Queue carries (node, col). Left −1, right +1.
Overwrite per column
map[col] = node.val unconditionally — BFS visits top-down, so the final write per column is the bottom-most node.
Read columns in order
Output map values sorted by column key.
Solution & live demo
Common pitfalls
Guarding the write like a top view
if c not in seen:
seen[c] = node.valseen[c] = node.val
That's exactly the top-view rule and produces the top view instead. Bottom view wants the deepest node per column, which BFS delivers as the last write.
Using DFS and overwriting blindly
def dfs(node, c):
seen[c] = node.val
dfs(node.left, c - 1); dfs(node.right, c + 1)q = deque([(root, 0)]) # BFS, overwrite per column
DFS visits a deep left node before a shallower right one, so the last write isn't necessarily the deepest — the right subtree can overwrite a genuinely lower node. DFS works only if you also track and compare depth explicitly.
Returning values in insertion order
return list(seen.values())
return [seen[c] for c in sorted(seen)]
The output must run left to right by column. Insertion order follows the BFS visit sequence, which interleaves columns arbitrarily.
Edge cases
BFS order decides (the later one wins) — matching GFG's expected output.
Same code but write only if the column is unseen — first wins instead of last.