Flip Binary Tree To Match Preorder Traversal

medium binary tree dfs preorder

Problem

You are given the root of a binary tree with n nodes, where each node is uniquely valued from 1 to n, and a sequence voyage of the same length. By flipping the left and right subtrees of any number of nodes, you want the tree's preorder traversal to equal voyage. Return the list of node values you flipped (in any order). If it is impossible, return [-1].

Inputroot = [1,2,3], voyage = [1,3,2]

Output[1]

At node 1 the left child is 2 but voyage wants 3 next, so flip node 1. Then preorder visits 1, 3, 2 — a match.

tree (level-order, use x for null)

voyage (comma-separated)

def flipMatchVoyage(root, voyage):
    flips = []
    i = 0

    def dfs(node):
        nonlocal i
        if not node:
            return True
        if node.val != voyage[i]:
            return False
        i += 1
        if node.left and node.left.val != voyage[i]:
            flips.append(node.val)
            return dfs(node.right) and dfs(node.left)
        return dfs(node.left) and dfs(node.right)

    return flips if dfs(root) else [-1]

function flipMatchVoyage(root, voyage) {
  const flips = [];
  let i = 0;
  function dfs(node) {
    if (!node) return true;
    if (node.val !== voyage[i]) return false;
    i++;
    if (node.left && node.left.val !== voyage[i]) {
      flips.push(node.val);
      return dfs(node.right) && dfs(node.left);
    }
    return dfs(node.left) && dfs(node.right);
  }
  return dfs(root) ? flips : [-1];
}

class Solution {
    List<Integer> flips = new ArrayList<>();
    int i = 0;
    int[] voyage;

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        this.voyage = voyage;
        return dfs(root) ? flips : List.of(-1);
    }

    private boolean dfs(TreeNode node) {
        if (node == null) return true;
        if (node.val != voyage[i]) return false;
        i++;
        if (node.left != null && node.left.val != voyage[i]) {
            flips.add(node.val);
            return dfs(node.right) && dfs(node.left);
        }
        return dfs(node.left) && dfs(node.right);
    }
}

class Solution {
    vector<int> flips;
    vector<int> voyage;
    int i = 0;

    bool dfs(TreeNode* node) {
        if (!node) return true;
        if (node->val != voyage[i]) return false;
        i++;
        if (node->left && node->left->val != voyage[i]) {
            flips.push_back(node->val);
            return dfs(node->right) && dfs(node->left);
        }
        return dfs(node->left) && dfs(node->right);
    }
public:
    vector<int> flipMatchVoyage(TreeNode* root, vector<int>& v) {
        voyage = v;
        return dfs(root) ? flips : vector<int>{-1};
    }
};

Explanation

We want the tree's pre-order traversal to spell out voyage, and we are allowed to swap a node's two children. The key realization is that at each node the decision is forced — we never have to guess.

We walk the tree in pre-order with a pointer i into voyage. When we reach a node, it must equal voyage[i]. If it does not, no flips can fix it, so we return false. Otherwise we advance i and move on.

The clever bit: after consuming the node, the next value voyage[i] tells us which child must come first. If node.left exists but does not match voyage[i], then the right child must go first, so we record a flip of this node and recurse right then left. Otherwise we keep the natural order, left then right.

Example: root = [1,2,3], voyage = [1,3,2]. At node 1 we match and advance, now expecting 3. The left child is 2, not 3, so we flip node 1 and visit right (3) then left (2). That yields pre-order 1, 3, 2, and the answer is [1].

Each node is visited once with a forced choice, so the whole thing runs in O(n) time. If any value ever mismatches, we return [-1].

Time: O(n) Space: O(h)