580. Vertical Order Traversal of a Binary Tree
Give every node of a binary tree a grid position: the root sits at row 0, column 0; a left child sits one row down and one column to the left of its parent (row+1, col−1); a right child sits one row down and one column to the right (row+1, col+1).
Your function receives the root of the tree and must return its vertical order traversal: one list per column, columns reported from the leftmost column to the rightmost. Inside a column, nodes are ordered from the top row down; if two nodes occupy the same row and the same column, the smaller value comes first.
That tie rule makes the answer unique, so return exactly that ordering.
Example 1:
Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[9], [3, 15], [20], [7]]
Explanation: 9 is alone in column −1. Column 0 holds the root 3 (row 0) and 15 (row 2). 20 is in column 1 and 7 in column 2.
Example 2:
Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: [[4], [2], [1, 5, 6], [3], [7]]
Explanation: Nodes 5 and 6 both land on row 2, column 0 — 5's parent shifted it right, 6's parent shifted it left. Same cell, so the smaller value 5 is listed before 6, after the root 1 from row 0.
Constraints:
- 1 ≤ number of nodes ≤ 1000
- 0 ≤ Node.val ≤ 1000
Hints:
Every node's (row, column) pair is fixed by the path from the root: left edges do col−1, right edges do col+1, and every edge does row+1. One traversal can label all nodes.
Once each node is a (col, row, value) triple, the problem is pure sorting: what single sort key produces columns left-to-right, rows top-down, and value ties in order?
Sort the triples lexicographically by (col, row, value), then walk the sorted list and start a new output group every time col changes.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [3, 9, 20, null, null, 15, 7]
Expected output: [[9], [3, 15], [20], [7]]