Column / coordinate traversal
Tag each node with (column, row) while traversing, then group by column.
Column = parent column ± 1, so a map keyed by column collects each vertical line.
01The intuition
Start with what you would do by hand
Draw the tree 3 at the top, 9 to its lower left, 20 to its lower right, and 15 and 7 under 20. Now imagine vertical lines through the drawing. The leftmost line passes through 9. The next passes through 3 and 15, because 15 is one step right of 20 which is one step right of 3, so it comes back to the middle. Then 20, then 7. The vertical order is [[9], [3, 15], [20], [7]].
By hand you draw and look. The computer has no drawing, only parent-to-child links. We need to give each node a horizontal position without drawing.
Build the structure, one piece at a time
Piece one: a column number for every node. The root is at column 0. A left child is at its parent's column minus 1, a right child at plus 1. That is all a "drawing" is: 9 is at −1, 20 at +1, 15 at 1 − 1 = 0, 7 at 1 + 1 = 2.
Piece two: a map from column number to a list of nodes. Walk the tree; each time you reach a node, append it to the list for its column. Any walk works for the grouping, but the order within a column matters.
Piece three: breadth-first order. Walk level by level with a queue, pushing (node, column) pairs. Then nodes higher in the tree are appended to their column before nodes lower down, and within a level left before right, which is the order the problems want.
| Popped | Column | Map after |
|---|---|---|
| 3 | 0 | {0: [3]} |
| 9 | −1 | {−1: [9], 0: [3]} |
| 20 | 1 | {−1: [9], 0: [3], 1: [20]} |
| 15 | 0 | {−1: [9], 0: [3, 15], 1: [20]} |
| 7 | 2 | {−1: [9], 0: [3, 15], 1: [20], 2: [7]} |
Finally read the map from the smallest column to the largest. Keeping the minimum and maximum column seen lets you read columns in order without sorting the keys; if you do sort them, that is the O(n log n) in the cost.
Why it is correct
The column rule is exactly how a drawing places nodes: each edge moves one unit left or right. So two nodes are on the same vertical line in the drawing if and only if their column numbers are equal, and the map groups exactly the nodes on each line.
column(child) = column(parent) ± 1, so column(v) = (number of right steps) − (number of left steps) on the path from the root to v
Order inside a column: BFS pops nodes in non-decreasing depth, and left children before right children at the same depth, so appends happen top to bottom and left to right. One variant, Vertical Order Traversal of a Binary Tree, asks for ties at the same depth and column to be sorted by value; then store (row, value) with each node and sort inside the column.
Why it is fast
Each node is pushed and popped once and appended to one list: O(n). Reading the map by column from min to max is O(n) more. Sorting column keys costs O(n log n) in the worst case, and the tie-sorting variant can cost that too. Memory is the map plus the queue, O(n).
How to recognise it in an interview
"Vertical order", "columns", "top view", "what you see from above", "diagonal traversal". Say: "I will tag each node with a column that changes by ±1 per step, BFS so each column fills top to bottom, and group by column in a map." Binary Tree Vertical Order Traversal is the plain version. Vertical Order Traversal of a Binary Tree adds the sort-by-value tie rule. Boundary of Binary Tree is a cousin where the tags are "on the left edge", "leaf", "on the right edge" instead of a column.
02The idea in one line
Tag each node with (column, row) while traversing, then group by column.
Reach for it when: Vertical order, top view, boundary traversal, diagonal traversal.
Cost: O(n log n) time.
03The walk-through, step by step
The video works one example: Vertical Order of [3,9,20,null,null,15,7]. These are its captions in order, so you can follow without the video or check a step you missed.
- Tag every node with a column; the root sits at column 0
- Pop 3 at column 0: append it to column 0
- Child 9 gets column 0 − 1 = -1; enqueue it
- Child 20 gets column 0 + 1 = 1; enqueue it
- Pop 9 at column -1: append it to column -1
- Pop 20 at column 1: append it to column 1
- Child 15 gets column 1 − 1 = 0; enqueue it
- Child 7 gets column 1 + 1 = 2; enqueue it
- Pop 15 at column 0: append it to column 0
- Pop 7 at column 2: append it to column 2
- Read the map by column: [[9],[3,15],[20],[7]]
- One BFS plus a map keyed by column: O(n), sorted keys O(n log n)
04Asked at Google
5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Vertical Order Traversal of a Binary Tree | Hard | 33 | last 6 months |
| Diagonal Traverse | Medium | 33 | |
| Binary Tree Vertical Order Traversal | Medium | 28 | |
| Boundary of Binary Tree | Medium | 18 | |
| Print Binary Tree | Medium | 18 | last 6 months |
05Related patterns
Other patterns in Trees: Recursive DFS (post-order fold), Best path through each node, Level-order BFS, Root-to-leaf path carry, Lowest common ancestor, Build from traversals, Iterative traversal with a stack, Rerooting DP (sum over all roots), Post-order deletion / pruning, Tree as a graph (parent pointers), Tree DP: take or skip this node, Serialize / deserialize by BFS.