#971

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Flip Binary Tree To Match Preorder Traversal

Determine the minimum set of nodes to flip in a binary tree so its pre-order traversal matches a given voyage sequence.

Problem Statement

You are given the root of a binary tree with n uniquely valued nodes from 1 to n, along with a sequence voyage representing a desired pre-order traversal. Your task is to flip nodes in the tree so that its pre-order traversal matches voyage exactly.

Flipping a node swaps its left and right children. Determine the smallest set of nodes to flip so the tree matches the given voyage. If no sequence of flips can achieve this, return [-1].

Examples

Example 1

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

Output: [-1]

It is impossible to flip the nodes such that the pre-order traversal matches voyage.

Example 2

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

Output: [1]

Flipping node 1 swaps nodes 2 and 3, so the pre-order traversal matches voyage.

Example 3

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

Output: []

The tree's pre-order traversal already matches voyage, so no nodes need to be flipped.

Constraints

The number of nodes in the tree is n.
n == voyage.length
1 <= n <= 100
1 <= Node.val, voyage[i] <= n
All the values in the tree are unique.
All the values in voyage are unique.

Solution Approach

Use Depth-First Search with Voyage Index Tracking

Perform a DFS traversal of the tree, maintaining an index into voyage. At each node, compare the node's value with the current voyage value. If they differ, immediately return failure. This ensures the traversal only progresses when the tree matches the expected pre-order sequence.

Flip Nodes Strategically When Left Child Mismatch Occurs

If the current node has a left child and its value does not match the next voyage value, flip the left and right children. Record the current node as flipped. This aligns the subtree with the expected pre-order without unnecessary flips, minimizing the flip set.

Handle Failure Cases and Collect Results

After DFS, check if the traversal covered all voyage elements. If any mismatch remains, return [-1]. Otherwise, return the collected list of flipped node values. This guarantees the minimal necessary flips while detecting impossible scenarios efficiently.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

The algorithm visits each node once in DFS, so time complexity is O(N). Each recursive call uses stack space proportional to tree height, leading to O(N) space in the worst case for skewed trees.

What Interviewers Usually Probe

Expect questions about correctly tracking voyage index during recursive traversal.
Watch for prompts about minimal flip sets and early failure detection.
Interviewers may ask for explanations of why certain flips are necessary or redundant.

Common Pitfalls or Variants

Common pitfalls

Not updating the voyage index correctly during recursion, causing false failures.
Flipping nodes unnecessarily instead of only when the left child mismatches.
Failing to handle edge cases where matching the voyage is impossible, returning incorrect results.

Follow-up variants

Count the total number of flips needed instead of returning the flipped node list.
Return a boolean indicating if the voyage can be matched without returning nodes.
Apply the same approach to mirrored post-order or in-order sequences with flips.

FAQ

What is the primary strategy to solve Flip Binary Tree To Match Preorder Traversal?

The key is DFS traversal with a voyage index tracker, flipping nodes only when the left child does not match the next voyage value.

Can this problem be solved without recursion?

Yes, an iterative DFS using a stack can replicate the voyage index tracking and flipping logic, though recursion is simpler for clarity.

What should be returned if no flips can match the voyage?

Return [-1] immediately when a node value does not match the current voyage value, indicating an impossible alignment.

How do you minimize the number of flipped nodes?

Only flip a node when the left child does not match the next expected voyage value; unnecessary flips increase the set and break minimality.

What pattern does this problem primarily test?

It tests binary-tree traversal and state tracking, specifically ensuring pre-order traversal aligns with a given sequence using minimal subtree flips.

terminal

Solution

Solution 1: DFS

We can traverse the entire tree using depth-first search, using an index $i$ to record the current node's index in the $\textit{voyage}$ array. If the value of the current node does not equal $\textit{voyage}[i]$, it means that it is impossible to match after flipping, we mark $\textit{ok}$ as `false` and return immediately. Otherwise, we increment $i$ by $1$, then check if the current node has a left child. If it does not, or if the value of the left child equals $\textit{voyage}[i]$, we recursively traverse the current left and right children; otherwise, we need to flip the current node and then recursively traverse the current right and left children.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

# 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]:
        def dfs(root):
            nonlocal i, ok
            if root is None or not ok:
                return
            if root.val != voyage[i]:
                ok = False
                return
            i += 1
            if root.left is None or root.left.val == voyage[i]:
                dfs(root.left)
                dfs(root.right)
            else:
                ans.append(root.val)
                dfs(root.right)
                dfs(root.left)

        ans = []
        i = 0
        ok = True
        dfs(root)
        return ans if ok else [-1]

Continue Practicing

#968 binary tree cameras #965 univalued binary tree #979 distribute coins in binary tree