Solution: Flip Binary Tree To Match Preorder Traversal
Tags: algorithms, javascript, java, python
Published: 2021-03-29 12:39:17

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/discuss/1132676).*

---

#### [Leetcode Problem #971 (*Medium*): Flip Binary Tree To Match Preorder Traversal](https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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:
>
![Description Visual 1](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:||
|---:|---|
Input:|root = [1,2], voyage = [2,1]
Output:|[-1]
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2019/01/02/1219-01.png)
Explanation:|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]
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2019/01/02/1219-02.png)
Explanation:|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:|[]
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2019/01/02/1219-02.png)
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.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

In order to find out which nodes have to be flipped, we'll have navigate the binary tree from the root in a **pre-order traversal**, which is a form of **depth first search** (**DFS**), and compare the node values with the values in the voyage array (**V**).

As with most binary tree DFS solutions, the common solution will use a **recursive** approach. We can use top-level scoped answer array (**ans**) to store the flipped nodes as well as an index counter (**vix**) for the current index of **V** as we traverse through the binary tree.

For our recursive function (**dfs**), we'll need to first take care of the exit conditions when the recursive function reaches a null node or when we've already found a failure. Then, if the node value is not the one expected, we should set our answer to **[-1]**.

Since we'll need to have parent-level access when we decide on a necessary flip, we should take care of that now before calling the next round of recursion. We can simply check the left node value against the next index of **V**, and if they're not a match, we should account for the flip by updating **ans**.

Rather than actually flipping around nodes in the binary tree, however, we can simply simulate the flip by recursing the two branches in reverse order. Otherwise, we can proceed with normal pre-order traversal.

---

#### ***Implementation:***

Python doesn't deal as easily with top-level scoped variables, so we can just use the first element of our **ans** array as the **V** index (**vix**), and then pass a reference to **ans** in our recursive function.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
const flipMatchVoyage = function (root, V) {
    let ans = [], vix = 0
    const dfs = node => {
        if (!node || ans[0] === -1) return
        if (node.val !== V[vix++]) ans = [-1]
        else if (node.left && node.left.val !== V[vix]) {
            ans.push(node.val)
            dfs(node.right)
            dfs(node.left)
        } else {
            dfs(node.left)
            dfs(node.right)
        }
    }
    dfs(root)
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def flipMatchVoyage(self, root: TreeNode, V: List[int]) -> List[int]:
        ans = [0]
        def dfs(node, V, ans):
            if not node or ans[0] == -1: return
            if node.val != V[ans[0]]: ans[0] = -1
            else:
                ans[0] += 1
                if node.left and node.left.val != V[ans[0]]:
                    ans.append(node.val)
                    dfs(node.right, V, ans)
                    dfs(node.left, V, ans)
                else:
                    dfs(node.left, V, ans)
                    dfs(node.right, V, ans)
        dfs(root, V, ans)
        return ans[:1] if ans[0] == -1 else ans[1:]
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    int vix = 0;
    List<Integer> ans = new ArrayList<>();
    private void dfs(TreeNode node, int[] V) {
        if (node == null || (ans.size() != 0 && ans.get(0) == -1)) return;
        if (node.val != V[vix++])
            ans = new ArrayList<Integer>(Arrays.asList(-1));
        else if (node.left != null && node.left.val != V[vix]) {
            ans.add(node.val);
            dfs(node.right, V);
            dfs(node.left, V);
        } else {
            dfs(node.left, V);
            dfs(node.right, V);
        }
    }
    public List<Integer> flipMatchVoyage(TreeNode root, int[] V) {
        dfs(root, V);
        return ans;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
    int vix = 0;
    vector<int> ans;
    void dfs(TreeNode* node, vector<int>& V) {
        if (!node || (ans.size() && ans[0] == -1)) return;
        if (node->val != V[vix++]) ans = {-1};
        else if (node->left && node->left->val != V[vix]) {
            ans.push_back(node->val);
            dfs(node->right, V);
            dfs(node->left, V);
        } else {
            dfs(node->left, V);
            dfs(node->right, V);
        }
    }
public:
    vector<int> flipMatchVoyage(TreeNode* root, vector<int>& V) {
        dfs(root, V);
        return ans;
    }
};
```