Vertical Order Traversal of a Binary Tree
Hard· BFS· Sorting
Problem
Place the root at (row 0, column 0); a left child goes to (row + 1, column - 1) and a right child to (row + 1, column + 1). Return the values column by column from left to right, each column listed top to bottom, with nodes that share the same row and column ordered by value.
Examples
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Input: root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Nodes 5 and 6 share row 2 and column 0, so they are ordered by value after 1.
Constraints
- • 1 <= number of nodes <= 1000
- • 0 <= Node.val <= 1000
Hints & approach
Hint 1
Traverse the tree while carrying each node's (row, column).
Hint 2
Group by column, and inside a column sort by (row, value).
Approachtry the hints first
Run a DFS or BFS that records (column, row, value) for every node. Sort all triples by column, then row, then value. Walk the sorted list and start a new output group whenever the column changes. The sort dominates the cost.
Time O(n log n) · Space O(n)