Fewest Node Additions and Removals to Make a Binary Tree Perfect

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

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

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

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

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.