# Flip Binary Tree To Match Preorder Traversal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal)
Canonical: https://scaleengineer.com/dsa/problems/flip-binary-tree-to-match-preorder-traversal
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
---
## Problem
You are given the `root` of a binary tree with `n` nodes, where each node is uniquely assigned a value from `1` to `n`. You are also given a sequence of `n` values `voyage`, which is the **desired** [**pre-order traversal**](https://en.wikipedia.org/wiki/Tree%5Ftraversal#Pre-order) of the binary tree.

Any node in the binary tree can be **flipped** by swapping its left and right subtrees. For example, flipping node 1 will have the following effect:

![](https://assets.glich.co/dsa/flip-binary-tree-to-match-preorder-traversal/image0.jpg) 

Flip the **smallest** number of nodes so that the **pre-order traversal** of the tree **matches** `voyage`.

Return _a list of the values of all **flipped** nodes. You may return the answer in **any order**. If it is **impossible** to flip the nodes in the tree to make the pre-order traversal match_ `voyage`_, return the list_ `[-1]`.

**Example 1:**

![](https://assets.glich.co/dsa/flip-binary-tree-to-match-preorder-traversal/image1.png) 

**Input:** root = [1,2], voyage = [2,1]
**Output:** [-1]
**Explanation:** It is impossible to flip the nodes such that the pre-order traversal matches voyage.

**Example 2:**

![](https://assets.glich.co/dsa/flip-binary-tree-to-match-preorder-traversal/image2.png) 

**Input:** root = [1,2,3], voyage = [1,3,2]
**Output:** [1]
**Explanation:** Flipping node 1 swaps nodes 2 and 3, so the pre-order traversal matches voyage.

**Example 3:**

![](https://assets.glich.co/dsa/flip-binary-tree-to-match-preorder-traversal/image3.png) 

**Input:** root = [1,2,3], voyage = [1,2,3]
**Output:** []
**Explanation:** 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**.

# Approaches
## Brute Force with Backtracking
This approach explores all possible tree configurations that can be achieved by flipping nodes. For each node, we can either flip its children or not. We can use a recursive backtracking algorithm to explore these two choices at every node. We try to match the preorder traversal of the resulting tree with the given `voyage`. To find the minimum number of flips, we keep track of the flips for each valid configuration and return the one with the smallest size.
**Time:** O(2^N * N). In the worst case, we explore two branches at each of the N nodes. The extra `* N` factor can come from work done within each recursive call, like calculating subtree sizes. · **Space:** O(N) or O(N^2). The recursion depth can be up to O(N). If the `voyage` array is sliced in each call, space can become O(N^2). Using indices would keep it at O(N).
**Pros:** Guaranteed to find the optimal solution if one exists because it explores the entire search space.
**Cons:** Extremely inefficient with exponential time complexity, making it infeasible for N > 20.; Very complex to implement correctly, especially the logic for managing the `voyage` index and subtree sizes.; Requires backtracking, adding to implementation complexity.
### Explanation
This approach attempts to find the solution by exploring all possible tree configurations that can be achieved by flipping nodes. For each node in the tree, we have two choices: either flip its children or not. This creates a large search space of `2^k` possible tree structures, where `k` is the number of nodes with at least one child. We can implement this using a recursive backtracking algorithm. The function would explore both choices (flip vs. no-flip) at each node. - **No-Flip Choice**: The function would first attempt to match the traversal without flipping the current node's children. It would recursively call itself for the left child, and then for the right child with an index that accounts for the size of the left subtree. This requires pre-calculating or dynamically calculating subtree sizes to know how many elements of the `voyage` belong to the left subtree. - **Flip Choice**: If the no-flip path fails or if we are exploring all possibilities, the function would then try flipping the children. It would add the current node's value to a list of flips and recursively call itself, but this time for the right child first, then the left. After the recursive calls return, it would swap the children back to restore the tree's state (this is the 'backtracking' step). - The function would return the list of flips if a match is found, or an indicator of failure. To find the minimum number of flips, we would need to explore all successful paths and compare the number of flips in each. This approach is highly inefficient due to its exponential nature and is complex to implement correctly, particularly the logic for partitioning the `voyage` array between recursive calls. It serves as a theoretical baseline to appreciate the efficiency of a more optimized greedy approach.
### Algorithm
- Define a recursive function `solve(node, index)` that explores all possibilities and returns the minimum list of flips or a failure indicator. - Base cases: If `index` reaches the end of `voyage`, the path is successful. If `node` is null or `node.val` doesn't match `voyage[index]`, the path fails. - At each `node`, pre-calculate the size of its left and right subtrees to correctly partition the `voyage` array for recursive calls. - **Path 1 (No Flip):** Recursively call `solve` for the left child (`solve(node.left, index + 1)`) and then the right child (`solve(node.right, index + 1 + size(node.left))`). If successful, this gives one possible solution. - **Path 2 (Flip):** Add `node.val` to a temporary flip list. Swap `node.left` and `node.right`. Recursively call `solve` for the new left child (old right) and then the new right child (old left). If successful, this gives another solution. Swap the children back (backtrack). - Compare the solutions from both paths. Return the one with the minimum number of flips. If no path is successful, return a failure indicator.

## Greedy Depth-First Search (DFS)
This is an optimal approach that traverses the tree and the `voyage` array simultaneously. We use a single pass (DFS) through the tree. At each node, we check if its value matches the current expected value from the `voyage`. If it does, we then look at its left child. If the left child's value does not match the next value in the `voyage`, we know a flip is necessary. This greedy choice is safe because in a preorder traversal, if the left child is not what's expected, the only alternative is the right child (after a flip). If that also doesn't match, then no solution is possible.
**Time:** O(N), where N is the number of nodes in the tree. Each node is visited exactly once during the DFS traversal. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, H can be N, leading to O(N) space complexity. The result list also contributes O(N) space in the worst case.
**Pros:** Highly efficient, solving the problem in a single O(N) pass.; The greedy logic is relatively simple and directly follows the properties of preorder traversal.; Finds the minimum number of flips because a flip is only performed when absolutely necessary.
**Cons:** The recursive implementation could lead to a stack overflow for extremely deep trees, although the problem constraints (N <= 100) make this highly unlikely.; Requires careful state management, using either member variables or passing state through function parameters, to track the current index and the list of flips.
### Explanation
We can solve this problem greedily in a single pass using a Depth-First Search (DFS) traversal. The core idea is to traverse the tree and the `voyage` array simultaneously, making decisions at each node. We use a global index, `i`, to keep track of our current position in the `voyage` array. The algorithm proceeds as follows: - We start a preorder traversal from the root. - At any `node`, we first check if its value matches `voyage[i]`. If it doesn't, a match is impossible because the root of a subtree cannot be changed by flipping its children. In this case, we signal failure and stop. - If `node.val` matches `voyage[i]`, we increment `i` and prepare to visit the children. - According to preorder traversal, the next node to visit should be the left child. We look at `voyage[i]` (the next expected value). - If `node.left` exists and `node.left.val` is **not** equal to `voyage[i]`, it means the standard preorder sequence is incorrect. Our only option is to flip the children of the current `node`. - By flipping, the new left child becomes the original right child. So, after deciding to flip, we must traverse the original right child first, then the original left child. We add `node.val` to our list of flipped nodes. - If `node.left` does not exist, or if `node.left.val` **is** equal to `voyage[i]`, then no flip is needed at this node. We proceed with the standard preorder traversal order: left child, then right child. - If at any point a required match fails (e.g., we need to flip, but the right child's value also doesn't match `voyage[i]`), the entire process is deemed impossible. This greedy strategy works because the structure of preorder traversal imposes a strict order. Any deviation has at most one potential fix (a flip), and if that fix doesn't work, no other sequence of flips can salvage the traversal for the current subtree. Here is a Java implementation of this approach: 
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private List<Integer> flipped;
    private int index;
    private int[] voyage;

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        this.flipped = new ArrayList<>();
        this.index = 0;
        this.voyage = voyage;
        
        dfs(root);
        
        if (!flipped.isEmpty() && flipped.get(0) == -1) {
            List<Integer> result = new ArrayList<>();
            result.add(-1);
            return result;
        }
        
        return flipped;
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        
        if (!flipped.isEmpty() && flipped.get(0) == -1) {
            return;
        }

        if (node.val != voyage[index]) {
            flipped.clear();
            flipped.add(-1);
            return;
        }
        index++;

        if (node.left != null && index < voyage.length && node.left.val != voyage[index]) {
            flipped.add(node.val);
            dfs(node.right);
            dfs(node.left);
        } else {
            dfs(node.left);
            dfs(node.right);
        }
    }
}
```
### Algorithm
- Initialize an empty list `flipped_nodes` and a global index `i = 0` for the `voyage` array. - Define a recursive DFS function `dfs(node)`. - Inside `dfs(node)`: - If `node` is null, return. - If a failure has already been recorded (e.g., `flipped_nodes` contains -1), return immediately to stop further processing. - Check if `node.val` matches `voyage[i]`. If not, it's an impossible match. Clear `flipped_nodes`, add `-1` to it, and return. - If they match, increment `i`. - Check if a flip is necessary. The condition is: `node.left != null` and the next voyage value `voyage[i]` does not match `node.left.val`. - If a flip is needed: Add `node.val` to `flipped_nodes`. Then, recursively call `dfs(node.right)` followed by `dfs(node.left)` to match the flipped order. - If no flip is needed: Proceed with the standard preorder traversal by recursively calling `dfs(node.left)` followed by `dfs(node.right)`. - Start the entire process by calling `dfs(root)`. - After the traversal, check the final state of `flipped_nodes` and return it.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int i ; private boolean ok ; private int [] voyage ; private List < Integer > ans = new ArrayList <>(); public List < Integer > flipMatchVoyage ( TreeNode root , int [] voyage ) { this . voyage = voyage ; ok = true ; dfs ( root ); return ok ? ans : List . of (- 1 ); } private void dfs ( TreeNode root ) { if ( root == null || ! ok ) { return ; } if ( root . val != voyage [ i ]) { ok = false ; return ; } ++ i ; if ( root . left == null || root . left . val == voyage [ i ]) { dfs ( root . left ); dfs ( root . right ); } else { ans . add ( root . val ); dfs ( root . right ); dfs ( root . left ); } } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < int > flipMatchVoyage ( TreeNode * root , vector < int >& voyage ) { bool ok = true ; int i = 0 ; vector < int > ans ; function < void ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) { if ( ! root || ! ok ) { return ; } if ( root -> val != voyage [ i ]) { ok = false ; return ; } ++ i ; if ( ! root -> left || root -> left -> val == voyage [ i ]) { dfs ( root -> left ); dfs ( root -> right ); } else { ans . push_back ( root -> val ); dfs ( root -> right ); dfs ( root -> left ); } }; dfs ( root ); return ok ? ans : vector < int > { - 1 }; } };
```

### Python

```python
# 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 ]
```