Minimum Edits to a Perfect Binary Tree
Snowflake● MediumFULLTIMEPHONE SCREENProblem statement
A binary tree is perfect when every internal node has two children and every leaf has the same depth. An empty tree is also perfect.
Find the minimum number of operations needed to make the given tree perfect. For this exercise, one operation either adds one new leaf at an empty left or right child position, or deletes one current leaf. Each operation costs one. You may delete the root only when it is the only node left. You cannot move a node, promote its children, or delete an entire nonempty subtree in one operation. Left and right positions remain distinct.
The arrays left and right describe the tree. Node i has the child indices left[i] and right[i]; -1 means absent. The root is node 0 when the arrays are nonempty. Return the minimum operation count. In particular, a result of 0 answers the initial question: the input tree is already perfect.
Function
minEditsToPerfectTree(left: int[], right: int[]) → intExamples
Example 1
left = [1,-1,-1]right = [2,-1,-1]return = 0Both children are leaves at depth 1, so the tree is already perfect.
Example 2
left = [1,2,-1]right = [-1,-1,-1]return = 2Delete both non-root leaves one after another to keep only the root, costing 2. Alternatively, delete the deepest leaf and add a right child to the root, also costing 2.
Example 3
left = [1,3,-1,-1]right = [2,-1,-1,-1]return = 1Delete node 3. The remaining root and its two leaf children form a perfect tree.
Constraints
0 <= left.length = right.length <= 30000.- Every child is
-1or a valid node index. - A nonempty input describes one valid binary tree rooted at
0: every other node has exactly one parent and every node is reachable. Node indices need not follow traversal order. - Node values do not affect this task.