Return Binary Tree Nodes in Vertical Order
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Return Binary Tree Nodes in Vertical Order
A binary tree has nodes numbered from `0` through `n - 1`, with node `0` as the root. Arrays `left` and `right` contain child indices, where `-1` means no child, and `values[i]` is node `i`'s integer value.
Assign the root column `0`, every left child its parent's column minus `1`, and every right child its parent's column plus `1`. Return one list per column from leftmost to rightmost. Within a column, return nodes from top to bottom; when two nodes share both row and column, preserve their left-to-right breadth-first discovery order.
## Function Signature
```python
def vertical_order(
values: list[int],
left: list[int],
right: list[int],
) -> list[list[int]]:
...
```
## Constraints
- `0 <= n <= 100_000`
- `len(values) == len(left) == len(right) == n`
- When `n > 0`, the arrays describe one valid binary tree rooted at `0`.
- `-1_000_000_000 <= values[i] <= 1_000_000_000`.
## Example
```text
Input:
values = [3, 9, 8, 4, 0, 1, 7]
left = [1, 3, 5, -1, -1, -1, -1]
right = [2, 4, 6, -1, -1, -1, -1]
Output: [[4], [9], [3, 0, 1], [8], [7]]
```
```text
Input: values = [], left = [], right = []
Output: []
```
Quick Answer: Return a binary tree's nodes in vertical columns from left to right while preserving top-to-bottom and breadth-first tie order. The problem tests coordinate definitions, deterministic grouping, same-row tie behavior, empty trees, and efficient processing across as many as 100,000 nodes.
A binary tree has `n` nodes numbered `0` through `n - 1`, with node `0` as the root. You are given three equal-length arrays that describe it:
- `values[i]` is the integer value stored at node `i`.
- `left[i]` is the index of node `i`'s left child, or `-1` if it has none.
- `right[i]` is the index of node `i`'s right child, or `-1` if it has none.
Assign every node a **column**: the root sits in column `0`, a left child sits in its parent's column minus `1`, and a right child sits in its parent's column plus `1`.
Return one list of node **values** per non-empty column, with the columns ordered from leftmost (most negative) to rightmost (most positive).
Within a single column, order nodes from top to bottom — that is, by increasing depth, where the root has depth `0`. When two nodes share **both** the same column and the same depth, they must appear in left-to-right breadth-first discovery order: the one reached earlier by a level-by-level traversal that visits each level's nodes left to right, and enqueues each node's left child before its right child, comes first.
Skip columns that contain no nodes — the result contains only non-empty lists. If `n == 0` the tree is empty and the result is an empty list.
### Example 1
```text
values = [3, 9, 8, 4, 0, 1, 7]
left = [1, 3, 5, -1, -1, -1, -1]
right = [2, 4, 6, -1, -1, -1, -1]
-> [[4], [9], [3, 0, 1], [8], [7]]
```
The tree is a perfect tree of 7 nodes. Node `0` (value `3`) is at column `0`. Its children, node `1` (value `9`) and node `2` (value `8`), sit at columns `-1` and `1`. The four leaves land at columns `-2` (value `4`), `0` (value `0`), `0` (value `1`) and `2` (value `7`). Column `0` therefore holds three nodes: the root at depth `0`, then the two depth-`2` leaves. Those two leaves tie on both column and depth, so breadth-first discovery order decides: value `0` descends from node `1` and value `1` descends from node `2`, and node `1` is visited before node `2`, so `0` precedes `1`.
### Example 2
```text
values = []
left = []
right = []
-> []
```
An empty tree produces no columns.
Constraints
- 0 <= n <= 100000
- len(values) == len(left) == len(right) == n
- -1000000000 <= values[i] <= 1000000000
- left[i] and right[i] are each either -1 (no such child) or a node index in [0, n - 1]
- When n > 0, the three arrays describe exactly one valid binary tree rooted at node 0: every node other than the root has exactly one parent, there are no cycles, and every node is reachable from node 0
- Node values are not guaranteed to be distinct
Examples
Input: ([3, 9, 8, 4, 0, 1, 7], [1, 3, 5, -1, -1, -1, -1], [2, 4, 6, -1, -1, -1, -1])
Expected Output: [[4], [9], [3, 0, 1], [8], [7]]
Input: ([], [], [])
Expected Output: []
Hints
- You never need to materialise tree objects. The arrays are the tree — walk them by index and carry one extra number alongside each index.
- Pick a traversal order whose natural visiting sequence already matches 'top to bottom, then left to right'. If you choose it well, you can append values as you go and never sort within a column.
- Columns run negative as well as positive, so you cannot index an array by column directly. Group first, order the groups last.