Group Binary Tree Nodes by Vertical Column, Top to Bottom and Left to Right
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a binary tree, report its node values column by column. The root is at column 0 and row 0. A left child is one column to the left of its parent (column minus 1), a right child is one column to the right (column plus 1), and each child is one row below its parent.
Return one list per column, from the leftmost column to the rightmost. Within a column, list values from the top row to the bottom row. When two or more nodes share both a row and a column, list them in left-to-right order within that row.
### Function Signature
```python
def vertical_columns(tree: list[int | None]) -> list[list[int]]:
```
### Rules
- **Input format.** `tree` is the level-order serialization of the tree. `tree[0]` is the root; after it, entries are consumed two at a time as the left child and then the right child of each non-null node, in the order those nodes appear. `None` marks a missing child, children of missing nodes are not listed, and trailing `None` entries may be omitted. An empty list is an empty tree.
- **Left-to-right order within a row** is the order in which nodes of that row appear in the level-order serialization.
- Output one list for each column that contains at least one node; an empty tree returns `[]`.
### Constraints
- `0 <= number of nodes <= 100`
- `-100 <= node value <= 100`; values may repeat.
### Examples
**Example 1**
Input: `tree = [3, 9, 20, None, None, 15, 7]`
Output: `[[9], [3, 15], [20], [7]]`
Explanation: 9 is at column -1; 3 (row 0) and 15 (row 2, left child of 20) are at column 0; 20 is at column 1; 7 is at column 2.
**Example 2**
Input: `tree = [3, 9, 8, 4, 0, 1, 7]`
Output: `[[4], [9], [3, 0, 1], [8], [7]]`
Explanation: 0 (right child of 9) and 1 (left child of 8) are both at row 2, column 0. Node 0 comes before node 1 in that row, so column 0 is `[3, 0, 1]`.
**Example 3**
Input: `tree = []`
Output: `[]`
Overview: Return a binary tree's node values grouped by vertical column from left to right, ordering each column top to bottom and breaking ties within a row by left-to-right position. The tree arrives as a level-order list, and the task tests coordinate tracking during traversal and precise tie handling.
Given a binary tree, report its node values column by column. The root is at row 0, column 0. A left child is one column to the left of its parent (column - 1), a right child is one column to the right of its parent (column + 1), and every child is one row below its parent.
Return one list per column, ordered from the leftmost column to the rightmost. Within a column, list the values from the top row to the bottom row. When two or more nodes share both a row and a column, list them in left-to-right order within that row. Left-to-right order within a row is the order in which that row's nodes appear in the level-order serialization. Output one list for each column that contains at least one node; an empty tree returns `[]`. Every node contributes its value exactly once, so repeated values are kept, not merged.
**Input format.** `tree` is the level-order serialization of the tree. `tree[0]` is the root; after it, entries are consumed two at a time as the left child and then the right child of each non-null node, in the order those nodes appear. A null entry (`None` in Python, `null` in JavaScript and Java, `std::nullopt` in C++) marks a missing child, children of missing nodes are not listed, and trailing null entries may be omitted. An empty list is an empty tree.
**Example 1**
Input: `tree = [3, 9, 20, None, None, 15, 7]`
Output: `[[9], [3, 15], [20], [7]]`
Explanation: 9 is at column -1; 3 (row 0) and 15 (row 2, left child of 20) are at column 0; 20 is at column 1; 7 is at column 2.
**Example 2**
Input: `tree = [3, 9, 8, 4, 0, 1, 7]`
Output: `[[4], [9], [3, 0, 1], [8], [7]]`
Explanation: 0 (right child of 9) and 1 (left child of 8) are both at row 2, column 0. Node 0 comes before node 1 in that row, so column 0 is `[3, 0, 1]`.
**Constraints**
- `0 <= number of nodes <= 100`
- `-100 <= node value <= 100`; values may repeat.
- `tree` is a well-formed level-order serialization as described above; a non-empty `tree` has a non-null `tree[0]`.
- No value can exceed 2^31 - 1; every value fits in a 32-bit signed integer.
Constraints
- 0 <= number of nodes <= 100
- -100 <= node value <= 100; values may repeat.
- tree is a well-formed level-order serialization as described in the statement; a non-empty tree has a non-null tree[0].
- No value can exceed 2^31 - 1; every value fits in a 32-bit signed integer.
Examples
Input: ([],)
Expected Output: []
Explanation: Empty tree returns an empty list.
Input: ([5],)
Expected Output: [[5]]
Explanation: A single root forms one column.
Hints
- A node's column is its parent's column minus 1 for a left child and plus 1 for a right child, so every column can be worked out while the tree is read from the serialization.
- Children of missing nodes are not listed, so a child's position in the list is not a fixed function of its parent's index. Pair the entries with the non-null nodes in the order those nodes appear.
- Inside a column the order is row first, then position in the level-order serialization. Check that whatever order you visit nodes in respects both keys.