Vertical Order Traversal of a Binary Tree
Stamp every node's (col, row), then sort by col, row, value
Give every node an exact 2D coordinate instead of thinking about left/right moves: the root sits at (col 0, row 0), a left child is one column left and one row down, a right child is one column right and one row down. Collect every node's (col, row, val) triple with a single DFS pass, then sort the whole list by column, then row, then value — the value tiebreak is the only part a plain traversal order can't get right on its own, for the rare case where two nodes land on the exact same column and row.
Details
Animated on: root = [3,9,20,null,null,15,7] — return nodes grouped by vertical column left to right, top to bottom within a column, ties broken by value. Expected: [[9],[3,15],[20],[7]].
Problem:Vertical Order Traversal of a Binary TreeHard
Stamp every node's (col, row), then sort by col, row, value
step 1 / 14
Every node has an exact (col, row) coordinate: the root sits at (0, 0), a left move shifts col left by one and row down by one, a right move shifts col right by one and row down by one.
1FUNCTION verticalTraversal(root):2 triples <- []3 DFS(root, 0, 0, triples)4 SORT triples BY col, row, val5 RETURN GROUP triples BY col6FUNCTION DFS(node, col, row, triples):7 IF node = null: RETURN8 APPEND (col, row, node.val) TO triples9 DFS(node.left, col - 1, row + 1, triples)10 DFS(node.right, col + 1, row + 1, triples)
← / → step · space play · Home restart
Every step in words
Show all 14 steps
- Every node has an exact (col, row) coordinate: the root sits at (0, 0), a left move shifts col left by one and row down by one, a right move shifts col right by one and row down by one.
- Visit 3 at column 0, row 0. Record the triple (col=0, row=0, val=3) — its exact position never needs recomputing again.
- 3 is stamped (0,0) — one column left of a right move, one right of a left move, one row down either way.
- Visit 9 at column -1, row 1. Record the triple (col=-1, row=1, val=9) — its exact position never needs recomputing again.
- 9 is stamped (-1,1) — one column left of a right move, one right of a left move, one row down either way.
- Visit 20 at column 1, row 1. Record the triple (col=1, row=1, val=20) — its exact position never needs recomputing again.
- 20 is stamped (1,1) — one column left of a right move, one right of a left move, one row down either way.
- Visit 15 at column 0, row 2. Record the triple (col=0, row=2, val=15) — its exact position never needs recomputing again.
- 15 is stamped (0,2) — one column left of a right move, one right of a left move, one row down either way.
- Visit 7 at column 2, row 2. Record the triple (col=2, row=2, val=7) — its exact position never needs recomputing again.
- 7 is stamped (2,2) — one column left of a right move, one right of a left move, one row down either way.
- All 5 coordinates collected: [[0,0,3],[-1,1,9],[1,1,20],[0,2,15],[2,2,7]]. Sort by column first, then row, then value — that last tiebreak is what separates 3 and 15, which share column 0 and different rows, from any node that ever shares BOTH column and row with another.
- Sorted: [[-1,1,9],[0,0,3],[0,2,15],[1,1,20],[2,2,7]]. Reading columns from minimum (-1) to maximum (2) and taking each column's values in that sorted order gives [[9],[3,15],[20],[7]].
- Done: [[9],[3,15],[20],[7]]. Every node contributes exactly one triple and the sort is O(n log n), so the whole traversal costs O(n log n) time, O(n) space for the triples and output.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.