Bottom View of Binary Tree

The bottom view of a binary tree is what you would see if you lay underneath it and looked straight up: one node per vertical column, and from each column only the lowest node is visible. The trick that unlocks it is a single idea — the horizontal distance of a node.

        1
       / \
      2   3
     / \   \
    4   5   6

The slow way first

You could compute every node's horizontal distance, bucket nodes into columns, and then for each column scan all its nodes to find the one with the greatest depth. That works, but it means tracking depth for every node and doing extra passes to break ties within a column.

The question to ask: is there a traversal order that visits nodes top-to-bottom, so the last node I see in a column is automatically the lowest one? There is — a level-order (BFS) traversal. If I just overwrite a column's value every time I visit a node in it, the final value is whatever I saw last, which is the deepest.

The idea: BFS and let later nodes overwrite

Walk the tree breadth-first. Carry each node's horizontal distance (hd) alongside it in the queue: the root is hd = 0, a left child is hd − 1, a right child is hd + 1. Keep a map bottom from hd to a value, and for every node we pop, assign bottom[hd] = node.val.

Because BFS processes an entire level before the next, any node we visit later is at the same depth or deeper. So the last write wins, and the last write for a column is its lowest node. At the end, read the map by sorted hd.

The key insight: with BFS, no tie-breaking is needed. We never compare depths — the overwrite order does it for us.

Walk through it

Step through the animation. The columns are laid out by horizontal distance, so each hd is a vertical line. BFS visits 1, 2, 3, then 4, 5, 6. Watch the bottom map fill in. The decisive moment is visiting 5: its hd is 0, which already held the root 1, so bottom[0] is overwritten to 5. That single overwrite is why 5 — not 1 — appears in the final answer.

Pseudocode

if root is empty: return []
bottom = empty map        # hd -> value
queue = [(root, 0)]       # pairs of (node, horizontal distance)
while queue is not empty:
    node, hd = pop front of queue
    bottom[hd] = node.val           # last write wins (BFS = top-down)
    if node has a left child:  enqueue (left,  hd - 1)
    if node has a right child: enqueue (right, hd + 1)
return [bottom[hd] for hd in sorted keys of bottom]

The Python solution

from collections import deque
 
def bottom_view(root):
    if not root:
        return []
    bottom = {}                      # hd -> value (last wins)
    queue = deque([(root, 0)])       # (node, hd)
    while queue:
        node, hd = queue.popleft()
        bottom[hd] = node.val        # overwrite: lower row wins
        if node.left:
            queue.append((node.left, hd - 1))
        if node.right:
            queue.append((node.right, hd + 1))
    return [bottom[hd] for hd in sorted(bottom)]

• bottom maps a horizontal distance → the value of the node currently visible in that column.
• queue holds (node, hd) pairs; popleft makes it a FIFO, which gives us level-order traversal.
• Line 10 is the heart of the trick — an unconditional overwrite. We never check whether a column is already filled; BFS order guarantees the last write is the lowest node.
• Children are enqueued with hd - 1 (left) and hd + 1 (right), so the distance propagates down the tree.
• At the end we read the map by sorted hd to get the columns left to right.

Complexity

We visit every node once, so the traversal is O(n); sorting the distinct horizontal distances at the end costs O(k log k) where k is the number of columns. Extra space is O(n) for the queue and the map.

When this pattern shows up

Practice