Special Traversals
What is this?
A few tree problems don't care about the usual visiting orders at all — they want the output arranged by where things sit in space, like reading a tree column by column. The trick is to give every node a pair of coordinates (its row and column) as you walk through, completely ignoring the tree's shape. Once each node carries a position, the whole problem turns into something simple: sort the nodes by their coordinates.
💡 Fun fact: This is the same idea behind how a spreadsheet or a screen lays things out — every cell or pixel has a coordinate, so arranging them is just sorting by position.
🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.
Core idea: Some tree problems don't ask for inorder/preorder/level order at all — they ask for an output defined by position (columns, rows, diagonals). The trick is to stop thinking about tree shape and assign every node a coordinate, then the answer is just a multi-key sort of those coordinates.
Coordinates over shape
Once each node carries (row, col), the tree's branching is irrelevant — you collect tuples and sort. Getting the tie-break order exactly right (column, then row, then value) is where most solutions break.
The problem
- Vertical Order Traversal of a Binary Tree — assign
(row, col), group by column left-to-right, and within a column sort by row then by value for same-cell collisions.
Key takeaways
- Give nodes coordinates — a geometric output contract becomes a sort.
- Mind the tie-break — column, then row, then value; the value tie-break is the classic bug.
- Tree shape stops mattering once every node has a position.
- Why interviewers love it: it checks whether you can translate an unusual output spec into a precise comparator.
Problem: Vertical Order Traversal of a Binary Tree.
Vertical Order Traversal of a Binary Tree
Core idea: Stop thinking about tree shape and start thinking about coordinates. Give every node a
(row, col)— root at(0, 0), left child at(row+1, col-1), right child at(row+1, col+1)— then the answer is just those nodes grouped bycoland sorted, within each column, byrowand then byval. A tree question quietly became a multi-key sort.
Problem, rephrased
Imagine you're rendering an org chart in a web UI. The CEO sits dead center. Every report drawn to the left shifts one slot left and one row down; every report to the right shifts one slot right and one row down. Now your layout engine needs to draw the chart column by column, left edge to right edge, so it can place each box in the correct screen lane. Within a single lane (column), boxes are drawn top to bottom; and if two people land in the exact same slot — same row and same column — you break the tie by name (here, by value) so the layout is deterministic.
That is vertical order traversal. Concretely, assign coordinates:
- root →
(0, 0) - left child of a node at
(r, c)→(r+1, c-1) - right child →
(r+1, c+1)
Then return the node values grouped by column, from the smallest (leftmost) column to the largest (rightmost). Within a column, order nodes by increasing row; and when two nodes share the same row and same column, order them by increasing value.
Take the tree [3, 9, 20, null, null, 15, 7] (level order):
![Tree [3, 9, 20, null, null, 15, 7] with coordinates: 3 at (row 0, col 0), 9 at (1,-1), 20 at (1,1), 15 at (2,0), 7 at (2,2)](https://maangioassets.blob.core.windows.net/diagrams/coding-interview/101/chapters/tree-traversal/special-traversals/vertical-order-traversal-of-a-binary-tree-diagram-1.svg)
Coordinates: 3→(0,0), 9→(1,-1), 20→(1,1), 15→(2,0), 7→(2,2). Group by column:
| Column | Nodes in column (as (row, val)) |
Output (sorted by row, then val) |
|---|---|---|
-1 |
(1, 9) |
[9] |
0 |
(0, 3), (2, 15) |
[3, 15] |
1 |
(1, 20) |
[20] |
2 |
(2, 7) |
[7] |
Reading columns left to right: [[9], [3, 15], [20], [7]].
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson