LeetCode 971: Flip Binary Tree To Match Preorder Traversal

Problem Restatement

We are given a binary tree and an array voyage.

A flip operation at a node swaps its left and right children.

We need to flip the smallest number of nodes so that the preorder traversal of the tree becomes exactly equal to voyage.

Preorder traversal visits nodes in this order:

root
left subtree
right subtree

If it is possible, return the values of the flipped nodes. The values may be returned in any order. If it is impossible, return:

[-1]

The tree has n nodes, n == voyage.length, 1 <= n <= 100, and all values in the tree and in voyage are unique.

Input and Output

Example function shape:

def flipMatchVoyage(root: Optional[TreeNode], voyage: list[int]) -> list[int]:
    ...

Examples

Example 1:

root = [1, 2]
voyage = [2, 1]

Output:

[-1]

The preorder traversal must start with the root value 1, but voyage starts with 2. No flip can change the root value.

Example 2:

root = [1, 2, 3]
voyage = [1, 3, 2]

Output:

[1]

Flip node 1, so its children become 3 then 2. The preorder traversal becomes:

[1, 3, 2]

Example 3:

root = [1, 2, 3]
voyage = [1, 2, 3]

Output:

[]

The preorder traversal already matches voyage.

First Thought: Try Flip Choices

At each node, we could try two possibilities:

1. Do not flip the node.
2. Flip the node.

This gives many possible trees.

But we do not need to try both blindly. Preorder traversal tells us exactly which node must come next.

Key Insight

During preorder DFS, when we visit a node, its value must match the current value in voyage.

After visiting the current node, the next value in voyage should be the root of the next subtree we visit.

Normally, we visit the left child first.

So if the left child exists but its value does not match the next value in voyage, then the only possible way to match the voyage is to flip the current node and visit the right child first.

This gives a greedy rule:

if node.left exists and node.left.val != voyage[index]:
    flip this node
    visit right first, then left
else:
    visit left first, then right

If even this does not work, the match is impossible.

Algorithm

Use DFS with an index into voyage.

1. Start with index = 0.
2. Visit the current node.
3. If the node is None, return True.
4. If node.val != voyage[index], return False.
5. Move index forward.
6. If the left child exists and its value does not match the next expected value:
   • Record node.val as flipped.
   • Visit right child first.
   • Then visit left child.
7. Otherwise:
   • Visit left child first.
   • Then visit right child.
8. If DFS succeeds, return the recorded flips.
9. Otherwise, return [-1].

Correctness

Preorder traversal always visits the current node before its children. Therefore, when DFS reaches a node, its value must equal the current value in voyage. If it does not, no sequence of child flips can fix this mismatch, because flips never change node values or move a child above its parent.

After matching the current node, preorder must next visit one of its children, if any child exists. Without a flip, the left child is visited first. With a flip, the right child is visited first.

If the left child exists and does not match the next expected voyage value, then visiting the left child first cannot work. Since values are unique, the only possible child that can match next is the right child. Therefore, flipping the current node is forced.

If the left child already matches the next expected value, then no flip is needed at this node. Flipping would move a different child first and would break the required preorder order.

Thus, at every node, the algorithm makes the only valid choice. If the traversal completes, the recorded flips produce exactly voyage. If the algorithm fails, no valid flip sequence exists.

Complexity

Let n be the number of nodes.

The output list can contain up to n flipped node values.

Implementation

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def flipMatchVoyage(
        self,
        root: Optional[TreeNode],
        voyage: list[int],
    ) -> list[int]:
        flips = []
        index = 0

        def dfs(node: Optional[TreeNode]) -> bool:
            nonlocal index

            if node is None:
                return True

            if index >= len(voyage) or node.val != voyage[index]:
                return False

            index += 1

            if (
                node.left is not None
                and index < len(voyage)
                and node.left.val != voyage[index]
            ):
                flips.append(node.val)
                return dfs(node.right) and dfs(node.left)

            return dfs(node.left) and dfs(node.right)

        if dfs(root):
            return flips

        return [-1]

Code Explanation

We store flipped node values here:

flips = []

The variable index points to the next expected value in voyage:

index = 0

At each node, we first check the preorder match:

if index >= len(voyage) or node.val != voyage[index]:
    return False

If the current node matches, we consume that voyage value:

index += 1

Then we decide whether to flip.

If the left child exists but is not the next expected node:

if (
    node.left is not None
    and index < len(voyage)
    and node.left.val != voyage[index]
):

we must flip the current node. We record it:

flips.append(node.val)

and traverse right before left:

return dfs(node.right) and dfs(node.left)

Otherwise, we keep normal preorder:

return dfs(node.left) and dfs(node.right)

At the end:

if dfs(root):
    return flips

return [-1]

we return the flip list if successful, otherwise [-1].

Testing

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(values):
    if not values:
        return None

    root = TreeNode(values[0])
    queue = deque([root])
    i = 1

    while queue and i < len(values):
        node = queue.popleft()

        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1

        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1

    return root

def run_tests():
    s = Solution()

    root = build_tree([1, 2])
    assert s.flipMatchVoyage(root, [2, 1]) == [-1]

    root = build_tree([1, 2, 3])
    assert s.flipMatchVoyage(root, [1, 3, 2]) == [1]

    root = build_tree([1, 2, 3])
    assert s.flipMatchVoyage(root, [1, 2, 3]) == []

    root = build_tree([1, 2, 3, 4, 5])
    assert s.flipMatchVoyage(root, [1, 2, 5, 4, 3]) == [2]

    root = build_tree([1, 2, 3, None, None, 4])
    assert s.flipMatchVoyage(root, [1, 3, 4, 2]) == [1]

    print("all tests passed")

run_tests()

Test meaning: