Fewest Node Additions and Removals to Make a Binary Tree Perfect
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A binary tree is **perfect** when every node has either zero or two children and every leaf is at the same depth. The interview first asked whether a given binary tree is perfect and then, as a follow-up, how few node additions and removals turn a tree that is not perfect into a perfect one. Write a function that returns that minimum number of operations; it returns 0 exactly when the tree is already perfect.
The tree has `n` nodes numbered `0` to `n - 1`, with node `0` as the root. `left[i]` and `right[i]` are the indices of node `i`'s left and right children, or `-1` when that child is missing.
### Function Signature
```python
def min_operations_to_perfect(left: list[int], right: list[int]) -> int:
```
### Rules
- The source did not define an operation precisely; this version counts one operation per node added or removed:
- **add**: attach one new node in an empty left or right child position of an existing node;
- **remove**: delete one node that currently has no children.
- Operations never move a node: every node that remains keeps its position relative to the root.
- The final tree must be a non-empty perfect binary tree. A single node is a perfect tree.
- Only the shape of the tree matters; nodes carry no values.
### Constraints
- `1 <= n <= 10^5`, where `n = len(left) = len(right)`
- every `left[i]` and `right[i]` is `-1` or an index in `[1, n - 1]`
- every node other than `0` is the child of exactly one node, and node `0` is no node's child, so the arrays describe a single tree with `n` nodes
- the tree's height can be as large as `n - 1`, so a perfect tree as tall as the input can have far more than `2^63 - 1` nodes; the returned value itself is always less than `n`
### Examples
**Example 1**
```text
Input: left = [1, 3, 5, -1, -1, -1, -1]
right = [2, 4, 6, -1, -1, -1, -1]
Output: 0
```
Every internal node has two children and all four leaves are at depth 2, so the tree is already perfect.
**Example 2**
```text
Input: left = [1, 3, 5, -1, -1, -1]
right = [2, 4, -1, -1, -1, -1]
Output: 1
```
Node 2 has a left child but no right child. Adding that one node gives a perfect tree of height 2.
**Example 3**
```text
Input: left = [1, 2, -1]
right = [-1, -1, -1]
Output: 2
```
The tree is a chain of three nodes going left. Removing nodes 2 and 1 leaves a single node; removing node 2 and adding a right child to node 0 also works. No single operation makes the tree perfect.
Overview: Given a binary tree described by left and right child arrays, return the fewest single-node additions and leaf removals that turn it into a perfect binary tree, which is 0 exactly when it is already perfect. Tests tree traversal and reasoning about tree shape, including very deep, skewed trees.
A binary tree is **perfect** when every node has either zero or two children and every leaf is at the same depth. Given a binary tree, return the minimum number of node additions and removals that turn it into a perfect binary tree. The answer is `0` exactly when the tree is already perfect.
The tree has `n` nodes numbered `0` to `n - 1`, with node `0` as the root. `left[i]` and `right[i]` are the indices of node `i`'s left and right children, or `-1` when that child is missing.
### Operations
Each of the following counts as one operation:
- **add**: attach one new node in an empty left or right child position of an existing node;
- **remove**: delete one node that currently has no children.
Operations never move a node: every node that remains keeps its position relative to the root. The final tree must be a non-empty perfect binary tree; a single node is a perfect tree. Only the shape of the tree matters; nodes carry no values.
Return the minimum number of operations as an integer.
### Constraints
- `1 <= n <= 10^5`, where `n = len(left) = len(right)`
- every `left[i]` and `right[i]` is `-1` or an index in `[1, n - 1]`
- every node other than `0` is the child of exactly one node, and node `0` is no node's child, so the arrays describe a single tree with `n` nodes
- the tree's height can be as large as `n - 1`, so a perfect tree as tall as the input can have far more than `2^63 - 1` nodes; the returned value itself is always less than `n`
No input value and no returned value exceeds `2^31 - 1`, so Java and C++ use `int` for the arrays and the result. Only intermediate quantities, such as the number of nodes in a tall perfect tree, can be huge, even beyond 64-bit range.
### Example 1
```text
Input: left = [1, 3, 5, -1, -1, -1]
right = [2, 4, -1, -1, -1, -1]
Output: 1
```
Node 2 has a left child but no right child. Adding that one node gives a perfect tree of height 2.
### Example 2
```text
Input: left = [1, 2, -1]
right = [-1, -1, -1]
Output: 2
```
The tree is a chain of three nodes going left. Removing nodes 2 and 1 leaves a single node; removing node 2 and adding a right child to node 0 also works. No single operation makes the tree perfect.
Constraints
- 1 <= n <= 10^5, where n = len(left) = len(right)
- every left[i] and right[i] is -1 or an index in [1, n - 1]
- every node other than 0 is the child of exactly one node, and node 0 is no node's child, so the arrays describe a single tree with n nodes
- the tree's height can be as large as n - 1, so a perfect tree as tall as the input can have far more than 2^63 - 1 nodes; the returned value itself is always less than n
Examples
Input: ([1, 3, 5, -1, -1, -1, -1], [2, 4, 6, -1, -1, -1, -1])
Expected Output: 0
Explanation: Source example 1: a perfect tree of height 2 (7 nodes, all four leaves at depth 2) needs no operations.
Input: ([1, 3, 5, -1, -1, -1], [2, 4, -1, -1, -1, -1])
Expected Output: 1
Explanation: Source example 2: a perfect height-2 tree missing one last-level node (node 2's right child); adding it costs 1, while keeping height 1 costs 3 and height 0 costs 5.
Hints
- Operations never move a node, so the final perfect tree keeps the original root and sits on the original positions; think about which of its positions the input already fills.
- Try fixing the height of the final perfect tree first: which original nodes then have to go, and which empty positions have to be filled?
- Keeping only the root already costs n - 1 operations, so a very tall target can never win; avoid computing the size of a perfect tree whose height is in the thousands.