Report Tree Levels and Balanced Subtrees
Company: Netflix
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement `describe_balanced_nodes(values)` for a binary tree represented as a zero-based heap array. For an existing node at index `i`, its children are at `2*i + 1` and `2*i + 2`. A `null` slot means no node; a valid input never places an existing node below a missing parent.
A node's subtree is height-balanced when both child subtrees are height-balanced and their heights differ by at most one. The empty subtree has height `0` and a leaf has height `1`.
Return one integer record `[index, level, balanced_flag]` for every existing node, ordered by increasing array index. The root is at level `0`. Encode a balanced subtree as `1` and an unbalanced subtree as `0`, so the return type is a portable list of integer lists.
### Constraints
- `0 <= len(values) <= 200000`
- Every non-null value is an integer in `[-10^9, 10^9]`.
- Values need not be unique; use the array index as node identity.
- An empty input returns an empty list.
```hint Stress irregular shapes
Test a one-sided chain, a root with only one child, and missing children at different levels.
```
```hint Check depth robustness
The largest valid input should not fail solely because the tree is deep.
```
Quick Answer: Implement `describe_balanced_nodes(values)` for a binary tree represented as a zero-based heap array. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
The nullable array `values` represents a binary tree: children of existing index `i` are `2*i+1` and `2*i+2`. For every existing node, return `[index, level, balanced_flag]` in increasing index order. The root level is zero. A subtree is balanced when both children are balanced and their heights differ by at most one; encode balanced as one and unbalanced as zero.
Constraints
- 0 <= len(values) <= 200000; null denotes a missing node.
- Every non-null value is an integer from -10^9 through 10^9.
- No existing node appears below a missing parent, and array index is node identity.
- Return [index, level, balanced_flag] records in strictly increasing index order.
Examples
Input: ([],)
Expected Output: []
Explanation: An empty tree returns no records.
Input: ([7],)
Expected Output: [[0, 0, 1]]
Explanation: A singleton root is a balanced leaf at level zero.
Hints
- Test empty and singleton trees, roots with only a left or only a right child, and a one-sided chain.
- Include missing children at different levels and an unbalanced subtree below another node.
- Use duplicate and boundary values to confirm that only structure and indices determine the records.