Traverse a Binary Tree in Zigzag Level Order
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Return a binary tree's node values in zigzag level order: the root level is read left to right, the next level right to left, and subsequent levels alternate directions.
### Function Contract
Implement `zigzag_levels(values, children) -> list[list[int]]`.
`values[i]` is node `i`'s value. The equally sized array `children` contains pairs `[left, right]` of child identifiers, using `-1` for a missing child. If the tree is nonempty, node `0` is the root. Return one inner array per level, from the root downward, in that level's required direction.
### Constraints and Clarifications
The array encoding and bounds are explicit practice interface choices.
- `0 <= len(values) == len(children) <= 200000`.
- Values are integers between `-1000000000` and `1000000000`, inclusive, and may repeat.
- The input describes a valid binary tree with all nodes reachable from root `0`, no cycles, and exactly one parent for every nonroot node.
- A missing child occupies no output position.
- Return `[]` for an empty tree.
- Aim for `O(n)` time, excluding no part of the required output construction.
### Examples
```text
values = [10, 20, 30, 40, 50]
children = [[1, 2], [3, 4], [-1, -1], [-1, -1], [-1, -1]]
Output: [[10], [30, 20], [40, 50]]
```
```text
values = [7]
children = [[-1, -1]]
Output: [[7]]
```
```hint Separate level membership from display direction
First determine which nodes belong to one level. Changing how that level's values are written should not accidentally change which nodes belong to the next level.
```
Overview: Return binary-tree values level by level while alternating left-to-right and right-to-left order without changing level membership.
Read the full LinkedIn Software Engineer interview experience this question came from
You are given a binary tree encoded as two equally sized arrays. `values[i]` is the value of node `i`, and `children[i]` is a pair `[left, right]` of node identifiers for node `i`'s left and right child, where `-1` means that child is missing. If the tree is nonempty, node `0` is the root.
Implement `zigzag_levels(values, children)` and return the tree's node values in zigzag level order: one inner list per level, from the root level downward. The root level is read left to right, the next level right to left, and subsequent levels keep alternating direction. A missing child occupies no output position. Return `[]` for an empty tree.
All values fit in a signed 32-bit integer (no value exceeds 2^31-1), and no arithmetic on values is needed.
Example 1:
```text
values = [10, 20, 30, 40, 50]
children = [[1, 2], [3, 4], [-1, -1], [-1, -1], [-1, -1]]
Output: [[10], [30, 20], [40, 50]]
```
The root level is [10]; level 1 holds 20 and 30 and is read right to left; level 2 holds 40 and 50 and is read left to right.
Example 2:
```text
values = [7]
children = [[-1, -1]]
Output: [[7]]
```
Constraints:
- `0 <= len(values) == len(children) <= 200000`.
- Values are integers between `-1000000000` and `1000000000`, inclusive, and may repeat.
- Each `children[i]` is a pair `[left, right]`; each entry is `-1` or a node index in `[0, n-1]`.
- The input describes a valid binary tree with all nodes reachable from root `0`, no cycles, and exactly one parent for every nonroot node.
- Aim for `O(n)` time.
Constraints
- 0 <= len(values) == len(children) <= 200000
- -1000000000 <= values[i] <= 1000000000; values may repeat
- Each children[i] is [left, right] with each entry -1 (missing) or a node index in [0, n-1]
- The input is a valid binary tree: all nodes reachable from root 0, no cycles, exactly one parent for every nonroot node
- A missing child occupies no output position; return [] for an empty tree
- Aim for O(n) time
Examples
Input: ([], [])
Expected Output: []
Explanation: An empty tree returns an empty list.
Input: ([7], [[-1, -1]])
Expected Output: [[7]]
Explanation: A single root forms one level.
Hints
- First determine which nodes belong to one level, independently of the direction that level is written in.
- Changing how a level's values are written should not change which nodes, or in what order, make up the next level.
- The direction depends only on the level's depth, starting left to right at the root.