Minimum Flips in Binary Tree to Get Result

Problem Description

Welcome to the world of binary trees, where every node has a value and a purpose, but sometimes they just can’t seem to agree on what the final result should be. Imagine a family dinner where everyone has a different opinion on what to order. You have to flip some opinions (or nodes) to get everyone on the same page.

In this problem, you are given a binary tree where each node represents a logical operation: AND, OR, NOT, or XOR. Your task is to determine the minimum number of flips required to make the root of the tree evaluate to a specific boolean result.

So, if you ever thought flipping a coin was hard, try flipping nodes in a binary tree!

Code Solution


class Solution:
    def minimumFlips(self, root: TreeNode | None, result: bool) -> int:
        @functools.lru_cache(None)
        def dp(root: TreeNode | None, target: bool) -> int:
            """Returns the minimum flips to make the subtree root become target."""
            if root.val in (0, 1):  # the leaf
                return 0 if root.val == target else 1
            if root.val == 5:  # NOT
                return dp(root.left or root.right, not target)
            if root.val == 2:  # OR
                nextTargets = [(0, 1), (1, 0), (1, 1)] if target else [[0, 0]]
            elif root.val == 3:  # AND
                nextTargets = [(1, 1)] if target else [(0, 0), (0, 1), (1, 0)]
            else:  # root.val == 4 XOR
                nextTargets = [(0, 1), (1, 0)] if target else [(0, 0), (1, 1)]
            return min(dp(root.left, leftTarget) + dp(root.right, rightTarget)
                       for leftTarget, rightTarget in nextTargets)

        return dp(root, result)

Approach Explanation

The code uses a dynamic programming approach with memoization to minimize the number of flips. The dp function recursively calculates the minimum flips needed for each subtree based on the logical operation represented by the node. It considers all possible target values for the left and right children and combines their results to find the minimum flips required.

Time and Space Complexity

Complexity Type Complexity
Time Complexity O(N * 2H), where N is the number of nodes and H is the height of the tree.
Space Complexity O(N) for the memoization cache and the recursion stack.

Real-World Example

Imagine you are at a party where everyone is trying to decide on a game to play. Some want to play charades (AND), others want to play Pictionary (OR), and a few just want to sit and watch (NOT). You need to flip some people’s preferences to get a consensus on what game to play. Just like in the binary tree, you need to make the right flips to achieve the desired outcome!

Similar Problems