Pattern visualizer

Bottom View of Binary Tree

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. 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]..

BFS by column, unconditional overwrite — deepest wins

time O(n)space O(n)step 1 / 10

Call stack

queue: [1@0]

line 4

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

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap