Vertical Order Traversal of a Binary Tree
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Vertical Order Traversal of a Binary Tree
You are given the `root` of a binary tree. Return the **vertical order traversal** of its nodes' values — that is, the values grouped by column, from the leftmost column to the rightmost column.
Assign each node a **column index**: the root is at column `0`; for any node at column `c`, its **left** child is at column `c - 1` and its **right** child is at column `c + 1`.
Return a list of columns ordered from the **leftmost** column to the **rightmost** column. Within a single column, list node values from **top to bottom** (by depth / row). If two nodes share the **same row and the same column**, list them **left to right** — that is, in the order they are reached by a breadth-first (level-order) traversal.
## Input format
The tree is given as a level-order array where `null` marks a missing child. For example, `[3, 9, 20, null, null, 15, 7]` represents:
```
3
/ \
9 20
/ \
15 7
```
## Examples
- Input: `[3, 9, 20, null, null, 15, 7]`
Output: `[[9], [3, 15], [20], [7]]`
- Input: `[1, 2, 3, 4, 5, 6, 7]`
Output: `[[4], [2], [1, 5, 6], [3], [7]]`
(`5` is the left child of `2` and `6` is the left child of `3`; both land in column `0` on the same row, so they are listed left to right as `5, 6`.)
## Constraints
- The number of nodes is in the range `[0, 10^4]`.
- `-10^5 <= Node.val <= 10^5`.
- If the tree is empty, return an empty list.
## Required
Return the vertical order traversal as a list of lists of integers.
Quick Answer: This question evaluates a candidate's ability to combine tree traversal with coordinate-based grouping and tie-breaking logic. It tests understanding of breadth-first traversal, sorting, and handling nodes that share the same position, commonly used to assess data structure proficiency in coding interviews. It falls under coding and algorithms and requires practical implementation skill rather than purely conceptual knowledge.
You are given a binary tree encoded as a level-order array `level_order`, where `null` (Python `None`) marks a missing child. Return the **vertical order traversal** of its nodes' values: the values grouped by column, from the leftmost column to the rightmost column.
Assign each node a **column index**: the root is at column `0`; for any node at column `c`, its **left** child is at column `c - 1` and its **right** child is at column `c + 1`.
Order the columns from **leftmost** to **rightmost**. Within a single column, list values from **top to bottom** (by row/depth). If two nodes share the **same row and same column**, list them **left to right** — i.e., in the order they are reached by a breadth-first (level-order) traversal.
For example, `[3, 9, 20, null, null, 15, 7]` represents:
```
3
/ \
9 20
/ \
15 7
```
and returns `[[9], [3, 15], [20], [7]]`.
If the tree is empty, return an empty list.
Constraints
- The number of nodes is in the range [0, 10^4].
- -10^5 <= Node.val <= 10^5.
- The input is a level-order array where null (None) marks a missing child.
- If the tree is empty, return an empty list.
Examples
Input: ([3, 9, 20, None, None, 15, 7],)
Expected Output: [[9], [3, 15], [20], [7]]
Explanation: Columns: 9 at -1; 3 and 15 both at 0 (15 below 3); 20 at +1; 7 at +2. Emitted left to right.
Input: ([1, 2, 3, 4, 5, 6, 7],)
Expected Output: [[4], [2], [1, 5, 6], [3], [7]]
Explanation: 5 (left child of 2) and 6 (left child of 3) both land in column 0 on the same row, so they are listed left to right as 5, 6.
Input: ([],)
Expected Output: []
Explanation: Empty tree returns an empty list.
Input: ([5],)
Expected Output: [[5]]
Explanation: A single node sits alone in column 0.
Input: ([1, 2, None, 3],)
Expected Output: [[3], [2], [1]]
Explanation: Left-skewed tree: 1 at column 0, 2 at -1, 3 at -2.
Input: ([-1, -2, -3],)
Expected Output: [[-2], [-1], [-3]]
Explanation: Negative values: -2 (left) at column -1, -1 (root) at 0, -3 (right) at +1.
Hints
- Assign the root column 0; a left child is column c-1 and a right child is column c+1. Track (column, row) for every node.
- Rebuild the tree from the level-order array using a queue: for each dequeued node, the next two array slots are its left and right children (skip a slot when it is null, but still consume it).
- Do a breadth-first traversal. Because BFS visits nodes in non-decreasing row order and left-to-right within a row, appending each node to its column's bucket in BFS order already gives the correct within-column ordering — no per-column sort is needed.
- Finally, emit the column buckets in order of increasing column index (leftmost to rightmost).