971. Flip Binary Tree To Match Preorder Traversal

LeetCode ↗

Problem Editor Pattern Idea Example Code Complex Pitfalls

Problem Description

You have a binary tree where each node has a unique value from 1 to n. You're also given an array voyage that represents the desired pre-order traversal sequence of the tree.

In a pre-order traversal, you visit nodes in this order:

Visit the current node
Traverse the left subtree
Traverse the right subtree

You can perform a "flip" operation on any node, which swaps its left and right children. For example, if a node has left child A and right child B, after flipping, it will have left child B and right child A.

Your task is to find the minimum number of nodes to flip so that the pre-order traversal of the modified tree matches the given voyage array exactly.

Return a list containing the values of all nodes that need to be flipped. You can return these values in any order. If it's impossible to achieve the desired traversal through any combination of flips, return [-1].

For example, if you have a tree with root 1, left child 2, and right child 3, and the desired voyage is [1, 3, 2], you would need to flip node 1 to swap its children, making the pre-order traversal match the voyage.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Tree DFS?

This problem maps to Tree DFS through a short path in the full flowchart.

Preorder DFS compares the current voyage index; if the left child diverges, record a flip and recurse on the right child first.

Open in Flowchart

Show step-by-step reasoning

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

Yes: The problem involves a binary tree, which is a special type of graph with nodes (tree nodes) and edges (parent-child relationships).

Is it a tree?

Yes: The problem explicitly states we're working with a binary tree where each node has at most two children (left and right).

DFS

Yes: We arrive at DFS as the solution approach.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this problem.

This makes perfect sense because:

We need to traverse the tree in pre-order (a form of DFS traversal)
We need to visit each node and make decisions about flipping based on the expected voyage sequence
DFS allows us to process nodes in the exact order of pre-order traversal (root → left → right), which aligns perfectly with comparing against the given voyage array
At each node during DFS, we can check if the current traversal matches the expected voyage sequence and decide whether to flip the node's children

The DFS approach naturally handles the recursive nature of checking each subtree and making flip decisions based on whether the left child matches the next expected value in the voyage sequence.

Intuition

The key insight is that pre-order traversal visits nodes in a fixed order: root → left → right. When we traverse the tree, we must match the given voyage sequence exactly. If at any point the current node's value doesn't match what we expect in voyage, it's impossible to achieve the desired traversal.

Think about what happens when we're at a node during traversal. After visiting the current node (which must match voyage[i]), we need to decide which child to visit next. In normal pre-order, we'd go left then right. But what if the left child's value doesn't match the next expected value voyage[i+1]?

This is where flipping comes in. If the left child doesn't match but the right child does match voyage[i+1], we can flip the current node to swap its children. After flipping, the right child becomes the left child, allowing us to continue matching the voyage sequence.

The beauty of this approach is that we make greedy decisions during traversal. At each node, we check:

Does my value match the current position in voyage? If not, it's impossible.
Does my left child match the next position? If yes, proceed normally (left → right).
If not, but my right child matches the next position, flip and proceed (right → left).

We only need to track which nodes we flip and whether the entire traversal remains valid. If we can traverse the entire tree while matching every value in voyage, we return the list of flipped nodes. Otherwise, we return [-1].

This greedy strategy works because each node appears exactly once in the pre-order traversal, and we must match the voyage sequence in order. There's no benefit to delaying a flip decision - if we need to flip, we must do it immediately to match the expected sequence.

Pattern Learn more about Tree, Depth-First Search and Binary Tree patterns.

New to patterns?Most interview problems reduce to a handful of patterns. This video covers the main eight.

Solution Approach

We implement the solution using DFS traversal with a few key variables to track our progress:

Index Tracking (voyage_index): We maintain an index voyage_index that tracks our current position in the voyage array. As we visit each node in pre-order, we increment this index.
Validity Flag (is_valid): A boolean flag that becomes False if we encounter an impossible situation where no amount of flipping can match the voyage.
Answer List (flipped_nodes): Collects the values of all nodes that need to be flipped.

The DFS function works as follows:

Base Cases:

If the current node is None or is_valid is already False, return immediately
If the current node's value doesn't match voyage[voyage_index], set is_valid = False and return (impossible to match)

Core Logic: After confirming the current node matches voyage[voyage_index], we increment voyage_index and need to decide the traversal order:

Check the left child:
- If there's no left child (node.left is None), proceed with normal traversal
- If the left child's value equals voyage[voyage_index] (the next expected value), proceed with normal traversal: left → right
Need to flip:
- If the left child exists but doesn't match voyage[voyage_index], we need to flip this node
- Add the current node's value to flipped_nodes to record the flip
- Traverse in reversed order: right → left

The algorithm processes each node exactly once, making decisions greedily. After the complete traversal:

If is_valid remains True, return the list of flipped nodes (flipped_nodes)
If is_valid is False, return [-1] indicating it's impossible to match the voyage

This approach has O(n) time complexity where n is the number of nodes, as we visit each node once. The space complexity is O(h) for the recursion stack, where h is the height of the tree.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Consider this binary tree and voyage array:

Tree:           voyage = [1, 3, 4, 2]
      1
     / \
    2   3
       /
      4

We want to check if we can flip some nodes to make the pre-order traversal match [1, 3, 4, 2].

Step 1: Start at root (node 1)

Current position in voyage: voyage_index = 0
Does node 1 match voyage[0] (which is 1)? ✓ Yes
Increment voyage_index to 1
Check left child: node 2's value is 2, but voyage[1] is 3 (mismatch!)
Check right child: node 3's value is 3, which matches voyage[1] ✓
Decision: Flip node 1 to swap its children
Add 1 to our answer list: flipped_nodes = [1]
After flip, traverse right child first (which was originally right, now logically left)

Step 2: Visit node 3 (originally right child)

Current position: voyage_index = 1
Does node 3 match voyage[1] (which is 3)? ✓ Yes
Increment voyage_index to 2
Node 3 has only a left child (node 4)
Check left child: node 4's value is 4, and voyage[2] is 4 ✓ Match!
Proceed with normal traversal (left → right)

Step 3: Visit node 4

Current position: voyage_index = 2
Does node 4 match voyage[2] (which is 4)? ✓ Yes
Increment voyage_index to 3
Node 4 has no children, continue

Step 4: Visit node 2 (originally left child, now visited last due to flip)

Current position: voyage_index = 3
Does node 2 match voyage[3] (which is 2)? ✓ Yes
Increment voyage_index to 4
Node 2 has no children, traversal complete

Result:

All nodes matched successfully (is_valid = True)
We flipped node 1
Return [1]

The final tree after flipping node 1 has its children swapped:

After flip:
      1
     / \
    3   2
   /
  4

Pre-order traversal of flipped tree: 1 → 3 → 4 → 2, which matches our voyage exactly!

Solution Implementation

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7
8from typing import Optional, List
9
10class Solution:
11    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:
12        """
13        Determine which nodes need to be flipped to match the pre-order traversal with voyage.
14        Returns list of node values to flip, or [-1] if impossible.
15      
16        Args:
17            root: Root of the binary tree
18            voyage: Target pre-order traversal sequence
19          
20        Returns:
21            List of node values that need their children flipped, or [-1] if impossible
22        """
23      
24        def dfs(node: Optional[TreeNode]) -> None:
25            """
26            Perform DFS traversal and determine nodes that need flipping.
27          
28            Args:
29                node: Current node being processed
30            """
31            nonlocal voyage_index, is_valid
32          
33            # Base case: null node or already found invalid
34            if node is None or not is_valid:
35                return
36          
37            # Check if current node matches expected value in voyage
38            if node.val != voyage[voyage_index]:
39                is_valid = False
40                return
41          
42            # Move to next position in voyage
43            voyage_index += 1
44          
45            # Check if we need to flip children
46            # If left child is None or matches next expected value, traverse normally
47            if node.left is None or node.left.val == voyage[voyage_index]:
48                # Normal traversal: left then right
49                dfs(node.left)
50                dfs(node.right)
51            else:
52                # Need to flip: traverse right then left
53                flipped_nodes.append(node.val)
54                dfs(node.right)
55                dfs(node.left)
56      
57        # Initialize variables
58        flipped_nodes = []  # List to store nodes that need flipping
59        voyage_index = 0    # Current index in voyage array
60        is_valid = True     # Flag to track if matching is possible
61      
62        # Start DFS traversal
63        dfs(root)
64      
65        # Return result based on validity
66        return flipped_nodes if is_valid else [-1]
67

1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    // Current index in the voyage array during traversal
18    private int currentIndex;
19  
20    // Flag to track if matching is possible
21    private boolean isMatchingPossible;
22  
23    // Target voyage array to match
24    private int[] targetVoyage;
25  
26    // List to store node values where flips are performed
27    private List<Integer> flippedNodes;
28
29    /**
30     * Determines if we can match the given voyage by flipping subtrees.
31     * Returns list of node values where flips are needed, or [-1] if impossible.
32     * 
33     * @param root The root of the binary tree
34     * @param voyage The target pre-order traversal sequence
35     * @return List of node values to flip, or [-1] if matching is impossible
36     */
37    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
38        // Initialize instance variables
39        this.targetVoyage = voyage;
40        this.currentIndex = 0;
41        this.isMatchingPossible = true;
42        this.flippedNodes = new ArrayList<>();
43      
44        // Perform DFS traversal to check if matching is possible
45        performDFS(root);
46      
47        // Return result based on whether matching was successful
48        return isMatchingPossible ? flippedNodes : List.of(-1);
49    }
50
51    /**
52     * Performs depth-first search to match tree traversal with voyage array.
53     * Flips children when necessary and records flipped nodes.
54     * 
55     * @param node Current node being processed
56     */
57    private void performDFS(TreeNode node) {
58        // Base case: null node or matching already failed
59        if (node == null || !isMatchingPossible) {
60            return;
61        }
62      
63        // Check if current node matches expected value in voyage
64        if (node.val != targetVoyage[currentIndex]) {
65            isMatchingPossible = false;
66            return;
67        }
68      
69        // Move to next position in voyage array
70        currentIndex++;
71      
72        // Determine traversal order based on next expected value
73        if (node.left == null || node.left.val == targetVoyage[currentIndex]) {
74            // Normal order: left then right
75            performDFS(node.left);
76            performDFS(node.right);
77        } else {
78            // Flip required: traverse right then left
79            flippedNodes.add(node.val);
80            performDFS(node.right);
81            performDFS(node.left);
82        }
83    }
84}
85

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
15        // Track if the voyage matching is possible
16        bool is_possible = true;
17      
18        // Current index in the voyage array
19        int voyage_index = 0;
20      
21        // Store nodes where flips are performed
22        vector<int> flipped_nodes;
23      
24        // Define DFS function to traverse and match with voyage
25        function<void(TreeNode*)> dfs = [&](TreeNode* current_node) {
26            // Base case: null node or matching already failed
27            if (!current_node || !is_possible) {
28                return;
29            }
30          
31            // Check if current node matches expected value in voyage
32            if (current_node->val != voyage[voyage_index]) {
33                is_possible = false;
34                return;
35            }
36          
37            // Move to next position in voyage
38            ++voyage_index;
39          
40            // Determine traversal order based on next expected value
41            if (!current_node->left || current_node->left->val == voyage[voyage_index]) {
42                // Normal order: left then right
43                dfs(current_node->left);
44                dfs(current_node->right);
45            } else {
46                // Flip required: traverse right then left
47                flipped_nodes.push_back(current_node->val);
48                dfs(current_node->right);
49                dfs(current_node->left);
50            }
51        };
52      
53        // Start DFS traversal from root
54        dfs(root);
55      
56        // Return result: flipped nodes if possible, otherwise [-1]
57        return is_possible ? flipped_nodes : vector<int>{-1};
58    }
59};
60

1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 *     val: number
5 *     left: TreeNode | null
6 *     right: TreeNode | null
7 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 *         this.val = (val===undefined ? 0 : val)
9 *         this.left = (left===undefined ? null : left)
10 *         this.right = (right===undefined ? null : right)
11 *     }
12 * }
13 */
14
15/**
16 * Determines if we can traverse the binary tree in the order specified by voyage,
17 * possibly by flipping some nodes' children.
18 * 
19 * @param root - The root of the binary tree
20 * @param voyage - The target traversal order array
21 * @returns Array of node values where we flip children, or [-1] if impossible
22 */
23function flipMatchVoyage(root: TreeNode | null, voyage: number[]): number[] {
24    // Flag to track if the voyage is still valid
25    let isValidVoyage: boolean = true;
26  
27    // Current index in the voyage array
28    let voyageIndex: number = 0;
29  
30    // Array to store the values of nodes where we flip children
31    const flippedNodes: number[] = [];
32  
33    /**
34     * Performs depth-first search traversal while checking voyage match
35     * @param currentNode - The current node being processed
36     */
37    const performDFS = (currentNode: TreeNode | null): void => {
38        // Base case: null node or invalid voyage detected
39        if (!currentNode || !isValidVoyage) {
40            return;
41        }
42      
43        // Check if current node matches the expected value in voyage
44        if (currentNode.val !== voyage[voyageIndex++]) {
45            isValidVoyage = false;
46            return;
47        }
48      
49        // Determine traversal order based on next expected value
50        if (!currentNode.left || currentNode.left.val === voyage[voyageIndex]) {
51            // Normal order: traverse left then right
52            performDFS(currentNode.left);
53            performDFS(currentNode.right);
54        } else {
55            // Flipped order: record the flip and traverse right then left
56            flippedNodes.push(currentNode.val);
57            performDFS(currentNode.right);
58            performDFS(currentNode.left);
59        }
60    };
61  
62    // Start DFS traversal from root
63    performDFS(root);
64  
65    // Return result based on whether voyage was valid
66    return isValidVoyage ? flippedNodes : [-1];
67}
68

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) traversal of the binary tree. Each node is visited exactly once during the traversal. At each node, the algorithm performs constant time operations:

Comparing node.val with voyage[voyage_index] takes O(1)
Incrementing the index voyage_index takes O(1)
Checking conditions and potentially appending to the answer list takes O(1)
Making recursive calls (the calls themselves, not the work done in them)

Since we visit each of the n nodes exactly once and perform O(1) work at each node, the total time complexity is O(n).

Space Complexity: O(n)

The space complexity consists of two components:

Recursion call stack: In the worst case, the tree could be completely unbalanced (like a linked list), resulting in a recursion depth of O(n). Each recursive call uses O(1) space on the call stack, giving us O(n) space for the recursion stack.
Answer list: In the worst case, we might need to flip at every internal node. Since a binary tree with n nodes can have at most n-1 internal nodes, the answer list could contain up to O(n) elements.

Therefore, the total space complexity is O(n) + O(n) = O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Worrying About `voyage[voyage_index]` Going Out of Bounds

The check node.left.val == voyage[voyage_index] runs right after voyage_index is incremented, so it is natural to ask whether the index can run past the end of voyage. It cannot. The problem guarantees that voyage has exactly n entries, one per node, and each matched node increments voyage_index once. If node.left exists, it is a node that has not been matched yet, so at most n - 1 nodes have been matched and voyage_index <= n - 1. Extra bounds checks are harmless but not required.

2. Deciding the Flip From the Right Child

A tempting variation is to flip whenever the right child matches the next voyage value:

# WRONG: flips a node that has only a right child
if node.right is None or node.right.val != voyage[voyage_index]:
    dfs(node.left)
    dfs(node.right)
else:
    flipped_nodes.append(node.val)
    dfs(node.right)
    dfs(node.left)

Problem Case:

Tree: node 1 with only a right child 2, and voyage = [1, 2]
The pre-order traversal already matches, so the answer is []
The variation sees that the right child matches voyage[1] and records a flip at node 1, returning [1], which is not the minimum

Solution: Base the decision on the left child. A flip is needed only when the left child exists and does not match the next voyage value:

if node.left is None or node.left.val == voyage[voyage_index]:
    dfs(node.left)
    dfs(node.right)
else:
    flipped_nodes.append(node.val)
    dfs(node.right)
    dfs(node.left)

3. Returning the Partial Flip List After a Mismatch

Once any node fails to match its voyage value, no set of flips can produce the voyage. Returning flipped_nodes at that point gives a partial list instead of [-1].

Problem Case:

Tree: root 1 with left child 2 and right child 3, where node 2 has a left child 4; voyage = [1, 3, 4, 2]
At node 1, the left child 2 does not match voyage[1] = 3, so node 1 is recorded as flipped
Node 3 matches, but then node 2 is compared with voyage[2] = 4 and fails
Returning the partial list gives [1]; the correct answer is [-1]

Solution: Track failure with the is_valid flag, stop the search once it becomes False, and check it before returning:

return flipped_nodes if is_valid else [-1]

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: