Vertical Order Traversal of a Binary Tree
Hard · Trees · Hash Table · Tree · Depth-First Search · Breadth-First Search · Sorting · Binary Tree
Problem
Place the root of a binary tree at position (row, col) = (0, 0). A node at (row, col) has its left child at (row + 1, col - 1) and its right child at (row + 1, col + 1).
The vertical order traversal lists the columns from the leftmost to the rightmost. Within one column, nodes are ordered from top to bottom by row, and nodes that share the same row and column are ordered by value, smallest first.
Return the vertical order traversal as a list of columns.
Examples
Input: root = [8,3,10,1,6,9,14] Output: [[1],[3],[8,6,9],[10],[14]]
6 and 9 both sit at row 2, column 0, below 8, so they are listed by value.
Input: root = [5,4,2,None,1] Output: [[4],[5,1],[2]]
Node 1 is the right child of 4, which puts it in the root's column, one row lower.
Input: root = [1,2,3,4,5,6,7,None,None,9,8] Output: [[4],[2,9],[1,5,6],[3,8],[7]]
5 and 6 share row 2, column 0, so 5 comes first; their children 9 and 8 land in columns -1 and 1.
Constraints
- The tree has between 1 and 1000 nodes.
- 0 <= Node.val <= 1000
Approaches
- Baseline: scan all nodes once per column — time O(n · w + n log n) for w columns, O(n²) at worst, space O(n)
Follow-up
Without the "same place, sort by value" rule (ties kept left to right), a breadth-first walk already visits each column top to bottom, and a dictionary of lists needs no sort at all. The use cases below keep this grid but ask for one value per column: the bottom view, and the column sums.
Related problems
Start free on Cariara · Coding problems · System design studio
