Flip Binary Tree To Match Preorder Traversal: Greedy DFS Approach

LeetCode Flip Binary Tree To Match Preorder Traversal (Problem 971) asks you to flip nodes in a binary tree so that the preorder traversal matches a given voyage array. A flip swaps the left and right children of a node. Return the list of node values that were flipped, or [-1] if it is impossible.

The problem

You are given a binary tree where every node has a unique value and an array voyage that represents a target preorder traversal. You can flip any node, which means swapping its left and right children. Your goal is to find the minimum set of flips that makes the tree's preorder traversal match voyage. If no sequence of flips can produce the target, return [-1].

The key observation is that flipping is the only tool you have. You cannot rearrange nodes arbitrarily. You can only swap left and right at each node. So at every step during a DFS, you either continue as-is or flip and continue, and if neither works, the answer is impossible.

The approach

The strategy is a DFS that walks through both the tree and the voyage array simultaneously. You maintain a pointer idx into the voyage array. At each node you visit:

1. Check if node.val equals voyage[idx]. If not, the tree cannot match, so return [-1].
2. Increment idx (you have consumed this element of the voyage).
3. If the node has a left child and that left child's value does not equal voyage[idx], you know the left subtree would produce the wrong next value. The only option is to flip, swapping left and right children before continuing. Record this node's value in the result.
4. Recurse into the left child, then the right child (after any swap).

This is a greedy approach. At each node, the decision to flip or not is forced. If the left child matches the next voyage value, you go left first (normal preorder). If it does not match but the right child does, you must flip. If neither child matches, the answer is impossible.

Step-by-step walkthrough

Let's trace through the example root = [1, 2, 3] with voyage = [1, 3, 2]. The original preorder would be [1, 2, 3], which does not match. Watch how the algorithm detects the mismatch at node 1's left child and flips.

The algorithm found that node 1 needed a flip. After swapping children [2, 3] to [3, 2], the preorder traversal becomes [1, 3, 2], which matches the voyage.

The code

def flipMatchVoyage(root, voyage):
    result = []
    idx = [0]

    def dfs(node):
        if not node:
            return True
        if node.val != voyage[idx[0]]:
            return False
        idx[0] += 1
        if node.left and node.left.val != voyage[idx[0]]:
            result.append(node.val)
            node.left, node.right = node.right, node.left
        return dfs(node.left) and dfs(node.right)

    if dfs(root):
        return result
    return [-1]

Let's break this down:

• idx = [0] is a list so the nested function can mutate it. It tracks your position in the voyage array.
• At each node, you first verify that the current node's value matches the expected voyage value. If it does not, the tree cannot be fixed with flips alone, so you return False.
• After confirming the current node matches, you increment idx and look ahead. If the left child exists but its value does not equal the next expected voyage value, you flip the children and record the flip.
• The recursion then continues into left and right subtrees in order. Because you may have just swapped them, "left" after the swap is actually the original right child.
• If the DFS succeeds all the way through, you return the list of flipped node values. Otherwise, [-1].

Note that you use idx as a mutable list (or you could use a global variable or class attribute) because the index needs to persist across recursive calls. Each call to dfs consumes one element of the voyage and advances the pointer.

Complexity analysis

Time is O(n) because you visit every node exactly once. Each node does O(1) work: a comparison, possibly a swap, and advancing the index.

Space is O(h) where h is the height of the tree, due to the recursion stack. For a balanced tree, h = log n. For a skewed tree, h = n in the worst case.

The building blocks

Preorder traversal with constraints

This problem builds on the standard preorder traversal pattern (visit node, go left, go right) but adds a constraint: the traversal order must match a specific sequence. Instead of just collecting values, you are verifying and possibly correcting the order as you go. The same "process current node, then recurse left, then recurse right" skeleton appears here, with the addition of a shared index into the voyage array.

Greedy decisions during DFS

At every node, the algorithm makes a greedy decision: flip or do not flip. This works because the decision is forced by the data. If the left child does not match the next expected value, flipping is the only option. If flipping also cannot fix it (neither child matches), the problem is impossible. There is no need for backtracking or trying multiple possibilities because each decision point has at most one viable choice.

Edge cases

• Single node tree: if the root value equals voyage[0], the answer is [] (no flips needed). If not, return [-1].
• Root value does not match voyage[0]: impossible. Return [-1] immediately.
• No flips needed: the tree already produces the correct preorder. The result is an empty list [].
• Every internal node needs flipping: the algorithm handles this naturally, recording each flipped node as it goes.
• Left child is null: when the left child does not exist, the DFS skips it (returns True for null) and proceeds to the right child. No flip check is needed because node.left is null.

From understanding to recall

You just walked through a greedy DFS algorithm that makes deterministic flip decisions at each node. The logic is compact: check the current node against the voyage, look ahead at the left child, flip if needed, and recurse. It makes sense now. But will you be able to write this from scratch under pressure?

The core pattern here is preorder DFS with a shared index pointer into an external array. You have seen this same idea in problems like Construct Binary Tree from Preorder and Inorder Traversal, where a pointer advances through a sequence as you build or verify tree structure. Recognizing this pattern turns a medium-difficulty problem into a routine application of a known technique.

Spaced repetition helps you internalize these patterns. You practice writing the DFS with the index pointer, the left-child mismatch check, and the swap logic from memory. After a few reps, the structure becomes automatic.

Related posts

• Binary Tree Preorder Traversal - Foundation for understanding the traversal order this problem targets.
• Invert Binary Tree - Related tree manipulation, though inverting flips every node while this problem selectively flips.
• Construct Binary Tree from Preorder and Inorder Traversal - Another problem connecting preorder sequences to tree structure.