Flip Binary Tree To Match Preorder Traversal

Flip Binary Tree To Match Preorder Traversal - 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 swap its left and right children.

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].

Input & Output

Example 1 — Need to Flip Root

$ Input: root = [1,2], voyage = [1,2]

› Output: []

💡 Note: Tree already matches voyage [1,2] with preorder traversal, no flips needed

Example 2 — Flip Required

$ Input: root = [1,2,3], voyage = [1,3,2]

› Output: [1]

💡 Note: Original preorder is [1,2,3], but we need [1,3,2]. Flip node 1 to swap children 2 and 3

Example 3 — Impossible Case

$ Input: root = [1,2,3], voyage = [1,2,4]

› Output: [-1]

💡 Note: Tree has node 3 but voyage expects node 4, which doesn't exist in tree

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

Visualization

Tap to expand

Understanding the Visualization

Input

Binary tree [1,2,3] and target voyage [1,3,2]

Process

Flip node 1 to swap its children

Output

Return [1] indicating which nodes were flipped

Key Takeaway

🎯 Key Insight: Compare preorder traversal with target and flip nodes when children don't match expected order

Asked in

G Google 15 a Amazon 8 M Microsoft 5

The key insight is to perform a preorder traversal while comparing with the expected voyage. When the left child doesn't match the expected next value, we need to flip the current node. The optimal approach uses DFS with early decision making: Time O(n), Space O(n).

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Backtracking	O(2^n)	O(n)	Use DFS traversal to make flip decisions on-the-fly
Try All Possible Flips	O(2^n × n)	O(n)	Generate all possible flip combinations and test each one

DFS with Backtracking — Algorithm Steps

Start DFS traversal from root
At each node, check if current value matches expected voyage position
If children don't match expected order, try flipping and continue
Backtrack if impossible to match

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin preorder traversal from root

Check Match

Compare current node with expected voyage

Decide Flip

Flip if children don't match expected order

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int* solution(int* root, int rootSize, int* voyage, int voyageSize, int* returnSize) {
    int* result = (int*)malloc(sizeof(int));
    result[0] = -1;
    *returnSize = 1;
    return result;
}

int main() {
    int root[] = {1, 2};
    int voyage[] = {1, 2};
    int returnSize;
    
    int* result = solution(root, 2, voyage, 2, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

In worst case, may need to try flipping every node, leading to exponential combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth plus space to store flip decisions

⚡ Linearithmic Space

32.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler