> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Flip Binary Tree To Match Preorder Traversal

> Tested Python solution for LeetCode 971 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 971, [Medium](/catalog/medium). Topics: [Tree](/catalog/topics/tree), [Depth-First Search](/catalog/topics/depth-first-search), [Binary Tree](/catalog/topics/binary-tree). [View on LeetCode](https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 971   # by problem number
lcpy gen -s flip_binary_tree_to_match_preorder_traversal   # by problem name
```

## 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** 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:

![Flip example](https://assets.leetcode.com/uploads/2021/02/15/fliptree.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]`.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2019/01/02/1219-01.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.leetcode.com/uploads/2019/01/02/1219-02.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.leetcode.com/uploads/2019/01/02/1219-02.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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/flip_binary_tree_to_match_preorder_traversal/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/flip_binary_tree_to_match_preorder_traversal/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from leetcode_py import TreeNode


class Solution:
    # Time: O(n)
    # Space: O(h)
    def flip_match_voyage(self, root: TreeNode[int] | None, voyage: list[int]) -> list[int]:
        flipped: list[int] = []
        idx = 0

        def dfs(node: TreeNode[int] | None) -> bool:
            nonlocal idx
            if node is None:
                return True
            if idx >= len(voyage) or node.val != voyage[idx]:
                return False
            idx += 1
            left, right = node.left, node.right
            if left is not None and right is not None:
                if idx >= len(voyage):
                    return False
                if left.val != voyage[idx] and right.val == voyage[idx]:
                    flipped.append(node.val)
                    left, right = right, left
            return dfs(left) and dfs(right)

        if root is None or not dfs(root) or idx != len(voyage):
            return [-1]
        return flipped
```

## Complexity

| Time | Space |
| - | - |
| O(n) | O(h) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.