Vertical Order Traversal
Vertical Order Traversal Of Binary Tree: group nodes by column (left child −1, right +1); within a column sort by row, ties by value.
- The number of nodes in the tree is in the range [1, 1000].
- 0 <= Node.val <= 1000
Intuition
The vertical order traversal of a binary tree groups nodes into columns, where moving to a left child shifts one column left and a right child shifts one right. Draw the tree on graph paper and read off the columns from left to right.
So every node has a two-dimensional coordinate: a column from the horizontal shifts, and a row from its depth. Collect a triple of (column, row, value) for each node with any traversal you like — the traversal order does not matter here, because the sorting at the end imposes the final order regardless.
What makes this harder than the top and bottom view problems is the tie-breaking, and the specification is exact about it:
- Columns are read left to right; within a column, nodes are ordered by row; and when two nodes share both a row and a column, the smaller value comes first.
That last rule is the one people miss. Two nodes genuinely can occupy the same cell — one arriving from the left subtree and one from the right — and the problem requires them sorted by value rather than by traversal order. Because of that, this cannot be solved by BFS ordering alone the way the top view can; the values have to be compared explicitly.
Once every node is a (column, row, value) triple, the whole problem reduces to sorting them and grouping by column.
Column index decreases left and increases right; row index increases downward. Collecting (row, value) per column and sorting handles the tie-break rule — same column and same row means order by value. Recording both coordinates up front is what lets one sort resolve every tie correctly.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n log n) time and O(n) space.
Give every node a row and a column
The root sits at (row 0, column 0). A left child inherits (row + 1, column - 1) and a right child (row + 1, column + 1). Both coordinates are needed — the column decides the group, and the row decides the order inside it.
Collect triples with any traversal
A single DFS or BFS gathers (column, row, value) for every node. The traversal order is irrelevant because the sort determines the output, which is a genuine simplification compared with the view problems where BFS order carries meaning.
Sort by column, then row, then value
Order the triples by all three fields in that priority. The value tiebreak is the specification's subtle requirement — two nodes can share a cell, and the problem demands the smaller value first rather than whichever was visited first.
Group the sorted triples by column
Walk the sorted list and start a new output group each time the column changes. Because the list is already sorted, each group emerges in the correct internal order with no further work.
Cost of the sort
Collecting the triples is O(n), and sorting them dominates at O(n log n). Space is O(n) for the triples and the output. Using a dictionary keyed by column and sorting each bucket separately gives the same bound while making the grouping step more explicit.
Solution & live demo
Common pitfalls
Ignoring the value tie-break
cols[c].append(node.val) # ... later: cols[c] stays in DFS order
cols[c].append((r, node.val)) # ... sorted(cols[c])
Two nodes can share a column and a row, and the problem demands the smaller value first. Storing only values leaves them in traversal order, which is arbitrary with respect to that rule.
Using BFS and assuming row order is enough
# BFS, append in visit order
cols[c].append((r, node.val)) sorted(cols[c])
BFS does give correct row ordering, but it still can't break same-cell ties by value without an extra sort. Since a sort is needed anyway, DFS with explicit coordinates is simpler and equally correct.
Iterating the column dict without sorting keys
return [cols[c] for c in cols]
return [... for c in sorted(cols)]
Dict iteration order reflects insertion, which follows the traversal, not the left-to-right column order the output requires. The keys must be sorted numerically.
Edge cases
The value tiebreak orders them — required by the problem.
Columns spread −n..0 or 0..n; dict handles sparse keys.