DSA Tracker

Visualize

Bottom View of Binary Tree

BFS by column, unconditional overwrite — deepest wins

time O(n)space O(n)

Give every node a column number: the root is column 0, a left step is column-1, a right step is column+1. Nodes that share a column stack up vertically, and the bottom view keeps only the deepest one per column. BFS visits shallower nodes before deeper ones, so if you walk the tree level by level and let a later visit to a column unconditionally overwrite an earlier one, whatever is left standing when the queue empties is exactly the deepest node in that column.

Details

Animated on: root = [1,2,3,null,5,null,7] — return the node values visible from below, one per vertical column, left to right. Expected: [2,5,3,7].

Problem:Bottom View of Binary TreeMedium

BFS by column, unconditional overwrite — deepest wins

step 1 / 10

2
5
1
3
7

Call stack

queue: [1@0]

Seed the queue with the root, 1, at column 0. Every left step moves a column left (col-1), every right step moves a column right (col+1) — that is the whole coordinate system.

Pseudocode
1FUNCTION bottomView(root):
2  IF root = null: RETURN []
3  colMap <- empty map
4  queue <- [(root, col=0)]
5  WHILE queue is not empty:
6    (node, col) <- DEQUEUE(queue)
7    colMap[col] <- node.val
8    IF node.left != null: ENQUEUE(queue, (node.left, col-1))
9    IF node.right != null: ENQUEUE(queue, (node.right, col+1))
10  RETURN values of colMap sorted by column

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. Seed the queue with the root, 1, at column 0. Every left step moves a column left (col-1), every right step moves a column right (col+1) — that is the whole coordinate system.
  2. Dequeue 1 at column 0. First node seen in this column, so it becomes column 0's current answer.
  3. 1's children (2@-1, 3@1) join the back of the queue, one column further out.
  4. Dequeue 2 at column -1. First node seen in this column, so it becomes column -1's current answer.
  5. 2's child (5@0) joins the back of the queue, one column further out.
  6. Dequeue 3 at column 1. First node seen in this column, so it becomes column 1's current answer.
  7. 3's child (7@2) joins the back of the queue, one column further out.
  8. Dequeue 5 at column 0. BFS visits level by level, so 5 is strictly deeper than whatever was there before — unconditionally overwrite: column 0 now reads 5 instead of 1.
  9. Dequeue 7 at column 2. First node seen in this column, so it becomes column 2's current answer.
  10. Queue empty. Read columns left to right, -1 to 0 to 1 to 2: bottom view = [2, 5, 3, 7]. Every node is enqueued and dequeued once, O(n) time; the column map holds O(n) entries.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Bottom View of Binary Tree in the editorAll Binary Trees problemsBack to roadmap