LeetCode Solutions Blog

Minimum Flips in Binary Tree to Get Result

Number: 2399

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

Given a binary tree where each leaf node has a boolean value (0 for false, 1 for true) and each non-leaf node represents a boolean operation (with values: 2 → OR, 3 → AND, 4 → XOR, and 5 → NOT), determine the minimum number of leaf flips needed so that the evaluation of the tree (starting at the root) equals a desired result. Note that NOT nodes have exactly one child while the other operators have two.

Key Insights

Use a DFS (depth-first search) recursion to evaluate the tree.
For each node, compute the minimum number of flips required to achieve both true and false outcomes.
For leaf nodes, if the value already matches the target boolean then cost is 0; otherwise it is 1 (flip required).
For internal nodes, combine the computed costs from its children based on the specific boolean operation.
For each operator, consider how its boolean logic propagates:
• OR: true if at least one child is true; false if both are false.
• AND: true only if both children are true; false if at least one is false.
• XOR: true if exactly one child is true; false if both are the same.
• NOT: simply inverts the child's value.
The answer is then derived by selecting the appropriate cost for the root based on the desired result.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes, since each node is processed once.
Space Complexity: O(h) where h is the height of the tree, due to the recursion stack.

Solution

The solution uses a DFS recursion where for each node we return two values: the minimum number of flips needed to make the subtree evaluate to true and to false. For leaves, these values are directly determined by whether a flip is needed. For non-leaf nodes, we combine the results from the child nodes based on the logic of the operator (OR, AND, XOR, or NOT). The key is to consider all possible ways of obtaining the desired result from the children, and then take the minimal cost among them.

Code Solutions

# 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

def minFlips(root, result):
    # Helper function to return a tuple (flips_to_true, flips_to_false)
    def dfs(node):
        if not node.left and not node.right:  # Leaf node
            if node.val == 1:
                return (0, 1)  # 0 flips to get True, 1 flip to get False
            else:
                return (1, 0)  # 1 flip to get True, 0 flips to get False
        if node.val == 5:  # NOT operator (only one child)
            child = node.left if node.left else node.right
            trueCost, falseCost = dfs(child)
            # NOT inverts the result.
            return (falseCost, trueCost)
        leftTrue, leftFalse = dfs(node.left)
        rightTrue, rightFalse = dfs(node.right)
        costTrue = float('inf')
        costFalse = float('inf')
        if node.val == 2:  # OR operator
            costTrue = min(leftTrue + rightTrue,
                           leftTrue + rightFalse,
                           leftFalse + rightTrue)
            costFalse = leftFalse + rightFalse
        elif node.val == 3:  # AND operator
            costTrue = leftTrue + rightTrue
            costFalse = min(leftFalse + rightTrue,
                            leftTrue + rightFalse,
                            leftFalse + rightFalse)
        elif node.val == 4:  # XOR operator
            costTrue = min(leftTrue + rightFalse,
                           leftFalse + rightTrue)
            costFalse = min(leftTrue + rightTrue,
                            leftFalse + rightFalse)
        return (costTrue, costFalse)
    
    trueCost, falseCost = dfs(root)
    return trueCost if result else falseCost

# Example usage:
if __name__ == "__main__":
    # Build sample tree: root = [3,5,4,2,null,1,1,1,0], desired result = True.
    # Constructing the tree manually.
    node2 = TreeNode(2, TreeNode(1), TreeNode(0))
    node5 = TreeNode(5, left=node2)
    node1_leaf = TreeNode(1)
    node1_leaf2 = TreeNode(1)
    node4 = TreeNode(4, left=node1_leaf, right=node1_leaf2)
    root = TreeNode(3, left=node5, right=node4)
    print(minFlips(root, True))  # Expected output: 2