Column-by-Column Report
HardTrees
Problem
Place a binary tree on a grid: the root sits at row 0, column 0; a node at (row, col) has its left child at (row + 1, col - 1) and its right child at (row + 1, col + 1).
Return the values column by column, from the leftmost column to the rightmost. Inside a column, list values from the top row down; when two or more nodes share both row and column, list them in increasing value.
Example 1
- Input:
- root = [3, 9, 20, null, null, 15, 7]
- Output:
- [[9], [3, 15], [20], [7]]
Column -1: 9. Column 0: 3 (row 0) then 15 (row 2). Column 1: 20. Column 2: 7.
Example 2
- Input:
- root = [1, 2, 3, 4, 6, 5, 7]
- Output:
- [[4], [2], [1, 5, 6], [3], [7]]
6 and 5 both sit at row 2, column 0, so they are listed by value: 5, 6.
Constraints
- 0 ≤ number of nodes ≤ 10^4
- 0 ≤ node.val ≤ 1000
Hint
Show the first hint
Every node gets a coordinate (row, col). Once you have all coordinates, what defines the output order?
Walkthrough
How to approach it
01Clarify before coding
- When do ties break by value? Only for nodes at the same row and column; same column but different rows go top-down.
- Can the same value appear twice in one cell? Yes, list both.
- Empty tree? Return [].
02Brute force
For each column from min to max, scan the whole tree and collect its nodes, then sort them by (row, value).
Cost: O(n · c) where c is the number of columns, up to O(n²) for a wide tree.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.