Minimum Flips in Binary Tree to Get Result

Minimum Flips in Binary Tree to Get Result - Problem

Imagine you have a binary expression tree where each leaf contains a boolean value (0 for false, 1 for true) and each internal node represents a boolean operation:

2 = OR operation
3 = AND operation
4 = XOR operation
5 = NOT operation (has only one child)

Your goal is to find the minimum number of leaf flips needed to make the entire tree evaluate to a desired result. A flip changes 0→1 or 1→0.

Key Challenge: You need to work backwards from the root, determining what each subtree should evaluate to in order to achieve the target result with minimum flips.

Input & Output

example_1.py — Basic OR Operation

$ Input: root = [2,0,1], result = false Tree: OR(0,1)

› Output: 1

💡 Note: The tree evaluates to true (0 OR 1 = true). To get false, we need both children false, so flip the right child: 1 flip needed.

example_2.py — AND with XOR

$ Input: root = [3,4,[0,1],1], result = true Tree: AND(XOR(0,1),1)

› Output: 0

💡 Note: XOR(0,1) = true, AND(true,1) = true. Already evaluates to true, so 0 flips needed.

example_3.py — NOT Operation

$ Input: root = [5,0], result = true Tree: NOT(0)

› Output: 0

💡 Note: NOT(0) = true. Already evaluates to the desired result, so 0 flips needed.

Constraints

The number of nodes in the tree is in the range [1, 10⁵]
Node values: 0, 1 for leaves, 2, 3, 4, 5 for internal nodes
NOT nodes have exactly one child, others have exactly two children
Leaf nodes have values 0 or 1 only
It is guaranteed that result can always be achieved

Visualization

Tap to expand

Understanding the Visualization

Identify Structure

Map out the boolean operations tree with leaves as switches

Calculate Leaf Costs

For each switch, determine flip cost for true/false

Combine Gate Costs

Work upward, calculating optimal costs for each gate

Find Optimal Path

Choose the minimum cost path to desired output

Key Takeaway

🎯 Key Insight: By calculating costs for both true and false outcomes at each node, we can optimally combine paths and avoid exploring all exponential possibilities, reducing complexity from O(2^n) to O(n).

Asked in

G Google 45 ⊞ Microsoft 32 f Meta 28 a Amazon 24

The optimal solution uses dynamic programming to calculate the minimum flips needed to make each subtree evaluate to both true and false. For each node, we compute costs based on its operation type and combine children's costs optimally. This achieves O(n) time complexity by avoiding redundant calculations, making it far superior to the exponential brute force approach.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Try All Combinations)	O(2^n × h)	O(h)	Try all possible combinations of leaf flips and find minimum
Dynamic Programming (Optimal)	O(n)	O(h)	Calculate minimum flips for both true and false at each node

Brute Force (Try All Combinations) — Algorithm Steps

Collect all leaf nodes in the tree
Generate all 2^n possible combinations of leaf values
For each combination, evaluate the tree from bottom up
Count flips needed and track minimum among valid results

Visualization

Tap to expand

Step-by-Step Walkthrough

Collect Leaves

Gather all leaf nodes from the tree

Generate Combinations

Create all 2^n possible leaf value combinations

Evaluate Each

Test each combination and count required flips

Find Minimum

Return the minimum flips among valid results

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

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

void collectLeaves(struct TreeNode* node, struct TreeNode** leaves, int* count) {
    if (!node) return;
    if (!node->left && !node->right) {
        leaves[(*count)++] = node;
    } else {
        collectLeaves(node->left, leaves, count);
        collectLeaves(node->right, leaves, count);
    }
}

bool evaluate(struct TreeNode* node) {
    if (!node->left && !node->right) {
        return node->val == 1;
    }
    
    switch (node->val) {
        case 2: // OR
            return evaluate(node->left) || evaluate(node->right);
        case 3: // AND
            return evaluate(node->left) && evaluate(node->right);
        case 4: // XOR
            return evaluate(node->left) != evaluate(node->right);
        case 5: // NOT
            {
                struct TreeNode* child = node->left ? node->left : node->right;
                return !evaluate(child);
            }
    }
    return false;
}

int minimumFlips(struct TreeNode* root, bool result) {
    struct TreeNode* leaves[1000];
    int leafCount = 0;
    collectLeaves(root, leaves, &leafCount);
    
    int minFlips = INT_MAX;
    
    // Try all 2^n combinations
    for (int mask = 0; mask < (1 << leafCount); mask++) {
        int originalVals[1000];
        int flips = 0;
        
        for (int i = 0; i < leafCount; i++) {
            originalVals[i] = leaves[i]->val;
            int newVal = (mask >> i) & 1;
            if (newVal != leaves[i]->val) flips++;
            leaves[i]->val = newVal;
        }
        
        if (evaluate(root) == result) {
            if (flips < minFlips) {
                minFlips = flips;
            }
        }
        
        // Restore original values
        for (int i = 0; i < leafCount; i++) {
            leaves[i]->val = originalVals[i];
        }
    }
    
    return minFlips;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × h)

2^n combinations where n is leaf count, h is height for evaluation

⚠ Quadratic Growth

Space Complexity

O(h)

Recursion stack for tree evaluation

✓ Linear Space

36.7K Views

Medium Frequency

~25 min Avg. Time

1.5K 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

Brute Force (Try All Combinations) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler