Skip to main content
Talentd

Minimum Flips in Binary Tree to Get Result - Solution & Explanation

HardPremiumFree on FleetCodeDynamic ProgrammingTreeDepth-First SearchBinary Tree20 min readAsked at: Google
Practice this problem

Problem Statement

You are given the root of a binary tree with the following properties:

  • Leaf nodes have either the value 0 or 1, representing false and true respectively.
  • Non-leaf nodes have either the value 2, 3, 4, or 5, representing the boolean operations OR, AND, XOR, and NOT, respectively.

You are also given a boolean result, which is the desired result of the evaluation of the root node.

The evaluation of a node is as follows:

  • If the node is a leaf node, the evaluation is the value of the node, i.e. true or false.
  • Otherwise, evaluate the node's children and apply the boolean operation of its value with the children's evaluations.

In one operation, you can flip a leaf node, which causes a false node to become true, and a true node to become false.

Return the minimum number of operations that need to be performed such that the evaluation of root yields result. It can be shown that there is always a way to achieve result.

A leaf node is a node that has zero children.

Note: NOT nodes have either a left child or a right child, but other non-leaf nodes have both a left child and a right child.

 

Example 1:

Input: root = [3,5,4,2,null,1,1,1,0], result = true
Output: 2
Explanation:
It can be shown that a minimum of 2 nodes have to be flipped to make the root of the tree
evaluate to true. One way to achieve this is shown in the diagram above.

Example 2:

Input: root = [0], result = false
Output: 0
Explanation:
The root of the tree already evaluates to false, so 0 nodes have to be flipped.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 105].
  • 0 <= Node.val <= 5
  • OR, AND, and XOR nodes have 2 children.
  • NOT nodes have 1 child.
  • Leaf nodes have a value of 0 or 1.
  • Non-leaf nodes have a value of 2, 3, 4, or 5.

Approach Overview

Problem Overview: You are given a binary tree representing a boolean expression. Internal nodes represent operators like AND, OR, XOR, or NOT, while leaves contain boolean values. You can flip a leaf value (0 to 1 or 1 to 0). The goal is to compute the minimum number of flips required so the entire tree evaluates to the desired result.

Approach 1: Brute Force Expression Re-evaluation (Exponential Time)

The naive idea is to try flipping different combinations of leaf nodes and re-evaluating the expression tree each time. For every subset of leaves, you flip values and run a full evaluation of the tree from the bottom up. If the root equals the target, track the minimum flips used. This requires exploring up to 2^L combinations where L is the number of leaves, and each evaluation costs O(n). The total time complexity becomes O(n * 2^L) with O(h) recursion space, which is impractical for large trees.

Approach 2: Tree DP + Case Analysis (O(n) time, O(h) space)

The optimal strategy uses dynamic programming on the tree with a postorder DFS. For each node, compute two values: the minimum flips needed for the subtree to evaluate to 0 and the minimum flips needed to evaluate to 1. For leaf nodes, the cost is straightforward: if the current value is already the target, cost is 0; otherwise 1. For internal nodes, combine results from children based on the operator type.

During DFS, each operator has specific cases. For example, an OR node becomes 1 if either child is 1, so the minimum cost is the minimum combination producing that state. For AND, both children must be 1. For XOR, children must differ. A NOT node simply swaps the costs of its child. By evaluating these combinations using constant-time comparisons, each node is processed once.

This approach naturally fits a Depth-First Search traversal over the Binary Tree. The DP state stores the minimal flips for both boolean outcomes, which is a common pattern in Dynamic Programming on trees. Since each node contributes constant work, the total time complexity is O(n) and space complexity is O(h) for the recursion stack.

Recommended for interviews: The Tree DP approach is what interviewers expect. The brute-force idea shows you understand the problem structure, but recognizing that each subtree only needs two DP states (cost for 0 and 1) demonstrates strong algorithmic thinking and comfort with DFS-based dynamic programming.

Solution

We define a function dfs(root), which returns an array of length 2. The first element represents the minimum number of flips needed to change the value of the root node to false, and the second element represents the minimum number of flips needed to change the value of the root node to true. The answer is dfs(root)[result].

The implementation of the function dfs(root) is as follows:

If root is null, return [+infty, +infty].

Otherwise, let x be the value of root, l be the return value of the left subtree, and r be the return value of the right subtree. Then we discuss the following cases:

  • If x \in {0, 1}, return [x, x \oplus 1].
  • If x = 2, which means the boolean operator is OR, to make the value of root false, we need to make both the left and right subtrees false. Therefore, the first element of the return value is l[0] + r[0]. To make the value of root true, we need at least one of the left or right subtrees to be true. Therefore, the second element of the return value is min(l[0] + r[1], l[1] + r[0], l[1] + r[1]).
  • If x = 3, which means the boolean operator is AND, to make the value of root false, we need at least one of the left or right subtrees to be false. Therefore, the first element of the return value is min(l[0] + r[0], l[0] + r[1], l[1] + r[0]). To make the value of root true, we need both the left and right subtrees to be true. Therefore, the second element of the return value is l[1] + r[1].
  • If x = 4, which means the boolean operator is XOR, to make the value of root false, we need both the left and right subtrees to be either false or true. Therefore, the first element of the return value is min(l[0] + r[0], l[1] + r[1]). To make the value of root true, we need the left and right subtrees to be different. Therefore, the second element of the return value is min(l[0] + r[1], l[1] + r[0]).
  • If x = 5, which means the boolean operator is NOT, to make the value of root false, we need at least one of the left or right subtrees to be true. Therefore, the first element of the return value is min(l[1], r[1]). To make the value of root true, we need at least one of the left or right subtrees to be false. Therefore, the second element of the return value is min(l[0], r[0]).

The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Leaf FlipsO(n * 2^L)O(h)Conceptual baseline when exploring all flip combinations on small trees
Tree DP + Case Analysis (DFS)O(n)O(h)General optimal solution; computes minimum flips for both boolean states per node

Video Solution

Leetcode Minimum Flips in Binary Tree to Get Result • Maximize Your Software Engineering Career • 3,869 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Minimum Flips in Binary Tree to Get Result easy or hard?
Minimum Flips in Binary Tree to Get Result is classified as Hard. The difficulty comes from modeling the boolean operators correctly and designing a tree DP that tracks both possible evaluation states. Once the DP state is defined, the implementation becomes a structured DFS with operator-specific case analysis.
Minimum Flips in Binary Tree to Get Result Python/Java solution
Implement a DFS that returns a pair of values: flips_to_zero and flips_to_one for each node. Leaf nodes return costs based on whether their value matches the target. Internal nodes combine child results using operator rules for AND, OR, XOR, and NOT. The same logic works in Python, Java, C++, Go, and TypeScript.
How to solve Minimum Flips in Binary Tree to Get Result in O(n)?
Run a postorder DFS and maintain two DP values for each node: the minimum flips needed for the subtree to evaluate to 0 and to 1. For leaves, the cost depends on whether the value matches the target. For internal nodes, combine children using operator logic (e.g., OR requires at least one child equal to 1). Each node performs constant work, leading to O(n) time.
What is the best approach for Minimum Flips in Binary Tree to Get Result?
Tree dynamic programming with a postorder DFS is the most efficient approach. For each node, compute the minimum flips needed for the subtree to evaluate to 0 and 1. Combine child states using operator-specific rules (AND, OR, XOR, NOT). This processes every node once for an overall O(n) time complexity.
Is Minimum Flips in Binary Tree to Get Result asked at Google/Amazon/Meta?
Boolean expression tree problems and tree dynamic programming patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving expression evaluation, DP on trees, and minimizing operations are common in high-level system and algorithm interviews.
What data structure is used in Minimum Flips in Binary Tree to Get Result?
The core data structure is a binary tree representing a boolean expression. The algorithm uses depth-first search along with dynamic programming states stored per node, tracking the minimum flips required for the subtree to evaluate to both possible boolean outcomes.
What is the time complexity of Minimum Flips in Binary Tree to Get Result?
The optimal Tree DP solution runs in O(n) time where n is the number of nodes in the tree. Each node is visited exactly once during a DFS traversal, and only constant-time case analysis is performed per node. Space complexity is O(h) due to the recursion stack, where h is the tree height.

Ready to solve this problem?

Practice Minimum Flips in Binary Tree to Get Result with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check If Two Expression Trees are Equivalent

Next

Design an Expression Tree With Evaluate Function