Vertical Order Traversal of a Binary Tree
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
