Given the root of a binary tree, return its bottom view — the set of nodes visible when the tree is viewed from directly below, ordered from left to right.
Assign each node a horizontal distance: the root is 0, a left child is one less than its parent, a right child one more. For each horizontal distance, the visible node is the lowest one (farthest from the root). If two nodes share a horizontal distance at the same depth, the one reached later in a top-down, left-to-right sweep is taken.
The tree is given in level-order (breadth-first), using null for missing children.
Input: root = [20, 8, 22, 5, 3, 4, 25] Output: [5, 8, 4, 22, 25] Columns by horizontal distance: -2 -> 5, -1 -> 8, 0 -> 4 (lowest at column 0), 1 -> 22, 2 -> 25.
Input: root = [1, 2, 3] Output: [2, 1, 3] Each of the three nodes is alone in its column.
- The number of nodes is in the range [0, 10^4] - 1 <= Node.val <= 10^5
The bottom view is the top view's twin: give each node a horizontal distance (root 0, left −1, right +1), then for each column keep the lowest node instead of the topmost. A level-order BFS visits nodes top-down, so simply overwrite each column's value as you go — the last node seen at a horizontal distance is the lowest.
“Which node in a column is visible?”
The lowest — greatest depth; BFS's last node at that column.
“Output order?”
By horizontal distance, left (most negative) to right (most positive).
Same setup as top view — assign horizontal distances and BFS top-down — but I overwrite each column instead of keeping the first.
The last node dequeued for each horizontal distance is the lowest, so that's the bottom view.
Worked example — tree [20, 8, 22, 5, 3, 4, 25]
20(0)
/ \
8(-1) 22(1)
/ \ / \
5(-2) 3(0) 4(0) 25(2)
hd -2: 5 hd -1: 8 hd 0: 4 (last at column 0) hd 1: 22 hd 2: 25
result: [5, 8, 4, 22, 25]
Whereas top view keeps the first node per column, bottom view keeps the last.
In BFS, unconditionally writing seen[hd] = val leaves the deepest (last) node standing.
Among nodes at the same depth in a column, BFS dequeues the more-right one later, so it wins.
| DFS tracking depth | BFS last-per-column | |
|---|---|---|
| Idea | Keep the greatest-depth node per hd | Overwrite each hd; last node wins |
| Time | O(n log n) | O(n log n) |
| Space | O(n) | O(n) |
Both sort by hd at the end; BFS just overwrites. Full code is in the Approaches selector below.
Key takeaway
Tag nodes with a horizontal distance, BFS top-down, and overwrite each column — the last node seen per column is the lowest. Output ordered by horizontal distance. O(n log n).
bfs with (node, hd):
seen[hd] = node.val # overwrite every time
enqueue (left, hd-1), (right, hd+1)
output seen[hd] for hd in sorted order