LeetCode 2313 - Minimum Flips in Binary Tree to Get Result

The problem presents a binary tree where leaf nodes represent boolean values 0 (false) or 1 (true), and internal nodes represent boolean operations OR, AND, XOR, and NOT, encoded as integers 2, 3, 4, and 5. You are also given a target boolean result.

leetcodeharddynamic-programmingtreedepth-first-searchbinary-tree

LeetCode Problem 2313

Difficulty: 🔴 Hard
Topics: Dynamic Programming, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem presents a binary tree where leaf nodes represent boolean values 0 (false) or 1 (true), and internal nodes represent boolean operations OR, AND, XOR, and NOT, encoded as integers 2, 3, 4, and 5. You are also given a target boolean result. The task is to determine the minimum number of flips required on leaf nodes so that evaluating the tree yields the target result.

Each operation is flipping a leaf node from 0 to 1 or vice versa. Non-leaf nodes compute values recursively based on their type and their children’s evaluations. OR, AND, and XOR nodes have two children, whereas NOT nodes have only one child. Leaf nodes cannot be flipped more than once.

The tree can be large, up to 100,000 nodes, so a naive approach that considers flipping every combination of leaf nodes would be computationally infeasible. The problem guarantees that it is always possible to achieve the desired result, so there is no need to handle impossible cases.

Important edge cases include trees with only one node (leaf), trees where all operations are NOT, or when the tree is already evaluated to the target. Handling NOT correctly is crucial because it only has one child, which changes the recursive evaluation.

Approaches

A brute-force approach would explore all possible combinations of leaf flips. For each combination, you would evaluate the tree recursively and check if it matches the target result. While correct in principle, this is exponentially slow since the number of leaf nodes can be large, making the approach infeasible for the problem constraints.

The optimal approach relies on dynamic programming on the tree. For each node, we compute two values: the minimum flips required for that subtree to evaluate to true and the minimum flips required to evaluate to false. Leaf nodes have straightforward values (0 requires 1 flip to become true, 1 requires 1 flip to become false). Internal nodes compute their true/false flip counts based on their operation and their children’s results. Using a post-order DFS ensures that the children’s values are computed before the parent, enabling bottom-up computation of minimum flips.

This reduces the problem to computing the minimum for each node in a single traversal, giving linear time complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^L * N) O(N) L = number of leaf nodes, evaluates all flip combinations, impractical
Optimal O(N) O(H) DFS with dynamic programming, H = height of tree, computes min flips bottom-up

Algorithm Walkthrough

  1. Define a DFS function that, for a given node, returns a tuple (min_flips_false, min_flips_true) representing the minimum flips to make the subtree evaluate to false or true.
  2. Base case for leaf nodes: If the node is a leaf, the minimum flips are 0 if the current value matches the target, and 1 if it does not. Specifically, for leaf value 0, flips to false is 0, flips to true is 1. For leaf value 1, flips to false is 1, flips to true is 0.
  3. Recursive computation for internal nodes:
  • Compute left and right flips for left and right children (if they exist). For NOT, only compute one child.
  • Depending on the operation (OR, AND, XOR, NOT), compute minimum flips for true and false based on boolean truth tables and combining child flip counts.
  1. Return the appropriate value: After DFS finishes, use the target boolean result to select the minimum flips from the root.
  2. DFS traversal ensures that each node is processed only once, propagating the optimal solution from the leaves to the root.

Why it works: Each node's minimum flip counts are computed based on its children. By using a post-order DFS, we ensure that when we compute a node, we already know the optimal flips for its children. This guarantees that the global minimum flips for the tree are obtained.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minimumFlips(self, root: Optional[TreeNode], result: bool) -> int:
        def dfs(node: Optional[TreeNode]) -> tuple[int, int]:
            if not node.left and not node.right:  # leaf node
                if node.val == 0:
                    return (0, 1)  # (flips to false, flips to true)
                else:
                    return (1, 0)
            
            if node.val == 5:  # NOT operation
                child_false, child_true = dfs(node.left or node.right)
                return (child_true, child_false)
            
            left_false, left_true = dfs(node.left)
            right_false, right_true = dfs(node.right)
            
            if node.val == 2:  # OR
                flips_true = min(left_true + right_true, left_true + right_false, left_false + right_true)
                flips_false = left_false + right_false
            elif node.val == 3:  # AND
                flips_true = left_true + right_true
                flips_false = min(left_false + right_false, left_false + right_true, left_true + right_false)
            elif node.val == 4:  # XOR
                flips_true = min(left_true + right_false, left_false + right_true)
                flips_false = min(left_true + right_true, left_false + right_false)
            else:
                raise ValueError("Invalid node value")
            
            return (flips_false, flips_true)
        
        flips_false, flips_true = dfs(root)
        return flips_true if result else flips_false

The Python implementation directly follows the DFS approach. Leaf nodes return (flips to false, flips to true) and internal nodes calculate combinations according to the boolean operation. The NOT operation is handled by swapping the child’s values. The root node’s tuple is then used to return the correct result based on the desired target.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minimumFlips(root *TreeNode, result bool) int {
    var dfs func(node *TreeNode) (int, int)
    dfs = func(node *TreeNode) (int, int) {
        if node.Left == nil && node.Right == nil {
            if node.Val == 0 {
                return 0, 1
            }
            return 1, 0
        }

        if node.Val == 5 { // NOT
            var childFalse, childTrue int
            if node.Left != nil {
                childFalse, childTrue = dfs(node.Left)
            } else {
                childFalse, childTrue = dfs(node.Right)
            }
            return childTrue, childFalse
        }

        leftFalse, leftTrue := dfs(node.Left)
        rightFalse, rightTrue := dfs(node.Right)

        var flipsFalse, flipsTrue int
        switch node.Val {
        case 2: // OR
            flipsTrue = min(leftTrue+rightTrue, leftTrue+rightFalse, leftFalse+rightTrue)
            flipsFalse = leftFalse + rightFalse
        case 3: // AND
            flipsTrue = leftTrue + rightTrue
            flipsFalse = min(leftFalse+rightFalse, leftFalse+rightTrue, leftTrue+rightFalse)
        case 4: // XOR
            flipsTrue = min(leftTrue+rightFalse, leftFalse+rightTrue)
            flipsFalse = min(leftTrue+rightTrue, leftFalse+rightFalse)
        }
        return flipsFalse, flipsTrue
    }

    flipsFalse, flipsTrue := dfs(root)
    if result {
        return flipsTrue
    }
    return flipsFalse
}

func min(a ...int) int {
    m := a[0]
    for _, v := range a[1:] {
        if v < m {
            m = v
        }
    }
    return m
}

The Go implementation mirrors the Python logic. Go handles nil instead of None. The min function is defined to take a variable number of arguments for easy computation.

Worked Examples

Example 1: root = [3,5,4,2,null,1,1,1,0], result = true

Traverse DFS post-order:

  1. Leaf nodes 1,1,1,0 return (1,0), (1,0), (1,0), (0,1) respectively.
  2. NOT node flips its child: (childFalse, childTrue) -> (childTrue, childFalse).
  3. XOR node combines children: compute min flips for true/false.
  4. AND node combines children: compute min flips.
  5. OR node (root) combines children.
  6. Extract flips_true at root → 2.

Example 2: root = [0], result = false

  1. Single leaf node: value 0 → (0,1).
  2. Result is false → return 0.