Return the Vertical Traversal of a Binary Tree
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
## Return the Vertical Traversal of a Binary Tree
### Problem
Implement `verticalTraversal(nodeValues, left, right, root) -> columns`.
Node `root` is at row `0`, column `0`. A left child is at `(row + 1, column - 1)`, and a right child is at `(row + 1, column + 1)`.
Return the node values grouped from the smallest column to the largest column. Within one column, order nodes by increasing row. When two nodes share both row and column, order their values in increasing numeric order.
### Function Contract
- Python: `def verticalTraversal(nodeValues: list[int], left: list[int], right: list[int], root: int) -> list[list[int]]`
- JavaScript: `function verticalTraversal(nodeValues, left, right, root)` returns a nested integer array.
- Java: `List<List<Integer>> verticalTraversal(List<Integer> nodeValues, List<Integer> left, List<Integer> right, int root)`
- C++: `vector<vector<int>> verticalTraversal(const vector<int>& nodeValues, const vector<int>& left, const vector<int>& right, int root)`
### Portable Contract
- The three arrays have the same length `n`, with `0 <= n <= 6,000`.
- Node IDs are `0` through `n - 1`. `left[i]` and `right[i]` are child IDs or `-1` when absent.
- When `n == 0`, `root == -1` and the result is empty. Otherwise `0 <= root < n`.
- For nonempty input, the child arrays describe one valid binary tree: every node is reachable from `root` exactly once, with no cycles or shared child.
- `-1,000,000,000 <= nodeValues[i] <= 1,000,000,000`; duplicate values are allowed.
- Do not modify any input array.
- Let `B` be the compact UTF-8 JSON byte length of `[nodeValues,left,right,root]`, with no whitespace and every bracket, comma, minus sign, and digit counted. Inputs satisfy `B <= 96,000`.
- Let `R` be the compact UTF-8 JSON byte length of the returned nested integer array under the same rule. Inputs guarantee `R <= 96,000`, so input plus output is at most `192,000` bytes.
- Target `O(n log n)` time and `O(n)` auxiliary space. Traversal must handle a height-`n` tree without depending on a shallow recursion limit.
### Examples
```text
nodeValues = [3, 9, 20, 15, 7]
left = [1, -1, 3, -1, -1]
right = [2, -1, 4, -1, -1]
root = 0
columns = [[9], [3, 15], [20], [7]]
```
```text
nodeValues = [1, 2, 3, 4, 5, 6, 7]
left = [1, 3, 5, -1, -1, -1, -1]
right = [2, 4, 6, -1, -1, -1, -1]
root = 0
columns = [[4], [2], [1, 5, 6], [3], [7]]
```
Nodes `5` and `6` share row `2`, column `0`, so their values are sorted.
```text
nodeValues = []
left = []
right = []
root = -1
columns = []
```
```hint Record coordinates during traversal
Once each node has a column and row, the output rule becomes an ordering problem over those records.
```
```hint Include every tie-breaker
Column determines the group, row determines vertical order, and value resolves nodes at the same coordinate.
```
### Discussion Requirements
1. Explain how coordinates propagate from parent to child.
2. State the complete sort key and how columns are grouped afterward.
3. Cover duplicate values, several nodes at one coordinate, an empty tree, one node, and a maximum-height tree.
4. Compare collecting and sorting all records with maintaining an ordered map of columns and rows.
Quick Answer: Return the vertical traversal of a binary tree using column, row, and value ordering with explicit tie rules. The exercise evaluates coordinate propagation, iterative handling of maximum-height trees, duplicate values, empty input, deterministic grouping, portable array representation, and sorting complexity.
Given a binary tree that is supplied as three parallel arrays plus a root id, return its node values grouped into vertical columns.
The tree has `n` nodes with ids `0` through `n - 1`. `nodeValues[i]` is the value stored at node `i`, `left[i]` is the id of node `i`'s left child, and `right[i]` is the id of its right child; a child id of `-1` means that child is absent. `root` is the id of the root node.
Place the root at row `0`, column `0`. A left child of a node at `(row, column)` sits at `(row + 1, column - 1)`, and a right child sits at `(row + 1, column + 1)`.
Return a list of columns, ordered from the smallest column number to the largest. Only columns that actually contain at least one node appear in the result. Within a single column, list node values by increasing row. When two nodes share the same row **and** the same column, list their values in increasing numeric order.
Note that node ids carry no ordering information: `root` is not necessarily `0`, and a node's id says nothing about its row or column. Also note that `-1` is a legal node **value** as well as the "no child" sentinel for `left` and `right`; the two uses are unrelated. Do not modify any of the input arrays.
### Output semantics
The result is fully determined. Sort every node by the triple `(column, row, value)` in ascending order, then emit one inner list per distinct column, in ascending column order, containing that column's values in that same sorted order. All three levels of the key are required.
### Examples
Example 1:
```text
nodeValues = [3, 9, 20, 15, 7]
left = [1, -1, 3, -1, -1]
right = [2, -1, 4, -1, -1]
root = 0
returns [[9], [3, 15], [20], [7]]
```
Node `0` (value `3`) is at `(0, 0)`. Node `1` (value `9`) is at `(1, -1)`, node `2` (value `20`) at `(1, 1)`, node `3` (value `15`) at `(2, 0)`, and node `4` (value `7`) at `(2, 2)`. The occupied columns are `-1, 0, 1, 2`, so the smallest column `-1` (holding `9`) is emitted first, then column `0` where `3` precedes `15` because row `0` precedes row `2`.
Example 2:
```text
nodeValues = [1, 2, 3, 4, 5, 6, 7]
left = [1, 3, 5, -1, -1, -1, -1]
right = [2, 4, 6, -1, -1, -1, -1]
root = 0
returns [[4], [2], [1, 5, 6], [3], [7]]
```
Values `5` and `6` both land at row `2`, column `0`, so the value tie-break puts `5` before `6`. Value `1` precedes both because it sits at row `0` of the same column.
Example 3 (empty tree):
```text
nodeValues = []
left = []
right = []
root = -1
returns []
```
Constraints
- nodeValues, left, and right all have the same length n, with 0 <= n <= 6000
- Node ids are 0 through n - 1; left[i] and right[i] are each either a child id in 0..n-1 or -1 when that child is absent
- When n == 0, root == -1 and the result is the empty list; otherwise 0 <= root < n (root is not necessarily 0)
- For nonempty input the child arrays always describe one valid binary tree: every node is reachable from root exactly once, with no cycles and no shared child
- -1000000000 <= nodeValues[i] <= 1000000000; duplicate values are allowed, and a nodeValue may itself be -1 (unrelated to the -1 child sentinel)
- Do not modify any input array
- Let B be the compact UTF-8 JSON byte length of [nodeValues, left, right, root], with no whitespace and every bracket, comma, minus sign, and digit counted; inputs satisfy B <= 96000
- Let R be the compact UTF-8 JSON byte length of the returned nested integer array under the same rule; inputs guarantee R <= 96000, so input plus output is at most 192000 bytes
- Target O(n log n) time and O(n) auxiliary space; traversal must handle a height-n tree without depending on a shallow recursion limit
Examples
Input: ([],[],[],-1)
Expected Output: []
Input: ([42],[-1],[-1],0)
Expected Output: [[42]]
Hints
- A node's row and column depend only on the path from the root, so you can compute every coordinate in one pass before thinking about the output at all.
- Column, then row, then value is a single combined ordering key rather than three separate passes. Once records are in that order, the column groups are already contiguous.
- n reaches 6000 and the tree may be one long chain, so carry each node's coordinate on an explicit stack or queue rather than relying on the language's call stack. Watch out for how your language orders negative keys if you group by column in a map.