2313. Minimum Flips in Binary Tree to Get Result

HardTreeDepth-First SearchDynamic ProgrammingBinary Tree
Leetcode Link

Problem Description

In this problem, we're given the root of a binary tree that represents a boolean expression. The leaves of this tree have values of either 0 or 1, which stand for the boolean values false and true, respectively. The non-leaf nodes can have one of four values: 2 (OR operation), 3 (AND operation), 4 (XOR operation), or 5 (NOT operation). The goal is to perform a minimum number of flips on the leaf nodes, where a flip changes a 0 to a 1 or a 1 to a 0, so that when the expression represented by the whole tree is evaluated, it yields the boolean value given by the variable result.

It's interesting to note that for the NOT operation, which is represented by the value 5, the tree node will have only one child. For all other operations, there will be two children.

The problem assures us that it is always possible to achieve the desired result through a series of flips. However, the challenge is to find the minimum number of flips needed to do so.

Intuition

To solve the problem, we must carefully navigate the tree and consider the cost (in terms of flips) of getting to the desired result. We'll need to perform a depth-first traversal of the tree. For each node, we need to consider two scenarios:

  • The number of flips required if the current node's evaluation needs to be true
  • The number of flips required if the current node's evaluation needs to be false

Because we are dealing with a boolean operation, we must consider the operation represented by each non-leaf node when computing the number of flips.

Here's the intuition behind the solution:

  • If we encounter a leaf node, the cost to make it true or false is straightforward: if the leaf node's current value is 0, it would take 0 flips to make it false and 1 flip to make it true, and vice versa for a leaf with a value of 1.

  • For non-leaf nodes, the situation is more complex, and we need to consider the operation represented by the node and the costs associated with flipping each of its children to make it either true or false.

The core of the solution is a recursive depth-first search that, for each node, returns a tuple (cost_to_true, cost_to_false) where:

  • cost_to_true is the minimum number of flips to make the current subtree evaluate to true.
  • cost_to_false is the minimum number of flips to make the current subtree evaluate to false.

Depending on the node's operation, we combine the costs of its children according to the boolean logic of OR, AND, XOR, and NOT.

Finally, the answer will be the cost associated with the root node to make its evaluation equal to the result. In the provided solution, this is implemented as dfs(root)[int(result)].

Learn more about Tree, Depth-First Search, Dynamic Programming and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Which algorithm should you use to find a node that is close to the root of the tree?

Solution Approach

The solution implements a recursive approach to traverse the tree and calculate the minimum number of flips required to achieve the desired result for each subtree. The algorithm uses Depth-First Search (DFS) which is a common tree traversal technique.

Here's how we implement the solution:

  • We define a recursive function called dfs which takes a node as input and returns a tuple (cost_to_true, cost_to_false). This tuple represents the minimum number of flips required to make the subtree rooted at the given node evaluate to true and false, respectively.

  • For a leaf node with value 0 or 1, the cost to make it true is its value (since 0 means false and 1 means true), and the cost to make it false is its complement (which is calculated by x ^ 1, where x is the value of the node).

  • For a non-leaf node, we recursively get the costs for its left and right children. The combined cost depends on the operation the non-leaf node represents:

    • OR (2): The minimum number of flips required to make the result true is simply the sum of flips for both children to be true. To make the result false, we need to have at least one child as false, so we take the minimum of either child being false or both being false.
    • AND (3): The flips to make the result true are the minimum required to get one or both children true. To make the result false, both children must be false, so we add both children's cost_to_false.
    • XOR (4): To maintain the true result, either one child should be true and the other false, so we take the two minimums accordingly. To make the result false, both children need to have the same evaluation, so we consider either both true or both false.
    • NOT (5): This operation flips the outcome, so we swap the costs for true and false of the single child node.

  • After calculating the costs for a node's children, we take the appropriate combination of costs as per the node's operation. Importantly, the solution ensures that results are mathematically minimized, taking advantage of the boolean nature of the problem to calculate the minimum number of steps.

  • The base case for the recursion is when we encounter a None type for a child node; we return (inf, inf) since we don't perform operations on non-existent children.

  • The function dfs(root)[int(result)] is used to extract the cost corresponding to the desired boolean result.

The solution leverages tuple unpacking, bitwise operations, and the recursive structure of the DFS algorithm, which makes it efficient and covers all edge cases due to its minimization logic at each step of the recursion.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the following binary tree representing a boolean expression:

1       2
2      / \
3     /   \
4    5     3
5   /     / \
6  1     1   0

In this tree:

  • The root node represents an OR operation (2).
  • The left child of the root is a NOT operation (5), with a leaf child of 1 (true).
  • The right child of the root is an AND operation (3), with two leaf children 1 (true) and 0 (false).

Let's say we want the final evaluated result of the tree to be true (1).

Here's how we walk through the solution approach:

  1. At the root (OR operation), we need to evaluate both the left and right subtrees.
  2. The left subtree is a NOT operation with a child leaf node of 1:
    • To make the NOT node true, since it's currently true, it would need to be flipped to false first, then NOT applied. That's 1 flip.
    • To make it false, we do nothing since NOT 1 is false. That's 0 flips.
  3. The right subtree is an AND operation with two leaf children 1 and 0:
    • To make the AND node true, we need both children to be true. In this case, we need 1 flip for the child 0 to become 1.
    • To make it false, we can choose either of the children to be false, which in this case requires 0 flips since the right child is already 0.
  4. Now, back at the root OR node, to make it true:
    • We can make either the left or the right subtree true. As per the calculated costs, making the left subtree true costs 1 flip, and making the right subtree true costs 1 flip as well. So, we would choose the minimum, which is 1 flip in this case.
    • We don't need to calculate the cost to make it false since the desired result is true.
  5. The minimum number of flips to get to the result is hence 1 which corresponds to flipping the leaf node from 0 to 1 in the right AND subtree.

By following the approach outlined in the solution, we recursively calculate the minimum number of flips and choose the optimal path at each step to achieve the desired boolean value with the least number of flips.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def minimumFlips(self, root: Optional[TreeNode], result: bool) -> int:
10        # Helper function to perform a depth-first search on the binary tree.
11        # This function will return a tuple with the minimum number of flips required
12        # to get the current subtree to evaluate to 0 and 1, respectively.
13        def dfs(node: Optional[TreeNode]) -> (int, int):
14            if node is None:
15                return float('inf'), float('inf')  # No flips can be done on a non-existent node
16              
17            # If node value is 0 or 1, no need to flip to obtain the same value,
18            # but one flip is needed to change it to the opposite value.
19            if node.val in (0, 1):
20                return node.val, node.val ^ 1
21          
22            # Recurse on the left and right subtrees.
23            left_flips, right_flips = dfs(node.left), dfs(node.right)
24          
25            # Calculate the minimum number of flips depending on the operation
26            # represented by the current node's value (AND, OR, XOR, NAND).
27            if node.val == 2:  # AND
28                return (left_flips[0] + right_flips[0],  # 0 AND 0
29                        min(left_flips[0] + right_flips[1], left_flips[1] + right_flips[0], left_flips[1] + right_flips[1]))  # 1 AND 1
30            if node.val == 3:  # OR
31                return (min(left_flips[0] + right_flips[0], left_flips[0] + right_flips[1], left_flips[1] + right_flips[0]),  # 0 OR 0
32                        left_flips[1] + right_flips[1])  # 1 OR 1
33            if node.val == 4:  # XOR
34                return (min(left_flips[0] + right_flips[0], left_flips[1] + right_flips[1]),  # 0 XOR 0
35                        min(left_flips[0] + right_flips[1], left_flips[1] + right_flips[0]))  # 1 XOR 1
36            # NAND operation (not standard, but assuming it's the opposite of AND)
37            return (min(left_flips[1], right_flips[1]),   # 0 NAND 0
38                    min(left_flips[0], right_flips[0]))   # 1 NAND 1
39
40        # Call the dfs helper function starting with the root of the tree.
41        # Convert the boolean result to an integer (0 or 1) to get the corresponding flips.
42        return dfs(root)[int(result)]
43
44# Note: It assumes that Optional[TreeNode] and float('inf') are already valid as per the Python 3 syntax.
45
1class Solution {
2    // Function to calculate the minimum flips to make the tree evaluate to the desired result
3    public int minimumFlips(TreeNode root, boolean result) {
4        // Call the DFS traversal and return the flips needed for the desired result (false: 0, true: 1)
5        return dfs(root)[result ? 1 : 0];
6    }
7
8    // DFS traversal to calculate minimum flips at each subtree
9    private int[] dfs(TreeNode node) {
10        // Base case: if the node is null, we return large numbers because there is nothing to flip
11        if (node == null) {
12            return new int[] {Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2};
13        }
14
15        // Leaf node condition, where value directly determines the number of flips (0 for no change, 1 for a flip)
16        int value = node.val;
17        if (value < 2) {
18            return new int[] {value, value ^ 1};
19        }
20
21        // Recurse on the left and right subtrees
22        int[] leftFlips = dfs(node.left);
23        int[] rightFlips = dfs(node.right);
24
25        // Initialize the minimum flips for making the current subtree true or false
26        int minFlipsFalse, minFlipsTrue;
27      
28        // Check the type of operator at the current node and calculate flips accordingly
29        if (value == 2) { // AND operator
30            minFlipsFalse = leftFlips[0] + rightFlips[0]; // Both subtrees should be false
31            minFlipsTrue = Math.min(Math.min(leftFlips[1] + rightFlips[0], leftFlips[0] + rightFlips[1]), leftFlips[1] + rightFlips[1]); // At least one subtree should be true
32        } else if (value == 3) { // OR operator
33            minFlipsFalse = Math.min(Math.min(leftFlips[0] + rightFlips[1], leftFlips[1] + rightFlips[0]), leftFlips[0] + rightFlips[0]); // At least one subtree should be false
34            minFlipsTrue = leftFlips[1] + rightFlips[1]; // Both subtrees should be true
35        } else if (value == 4) { // XOR operator
36            minFlipsFalse = Math.min(leftFlips[0] + rightFlips[0], leftFlips[1] + rightFlips[1]); // Subtrees should have same truth values
37            minFlipsTrue = Math.min(leftFlips[0] + rightFlips[1], leftFlips[1] + rightFlips[0]); // Subtrees should have opposite truth values
38        } else { // NOT operator (Assuming it's a unary operator on left subtree only)
39            minFlipsFalse = Math.min(leftFlips[1], rightFlips[1]); // The subtree should be true to propagate false upwards
40            minFlipsTrue = Math.min(leftFlips[0], rightFlips[0]); // The subtree should be false to propagate true upwards
41        }
42
43        // Return the minimum flips required to make the subtree true and false
44        return new int[] {minFlipsFalse, minFlipsTrue};
45    }
46}
47
1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    int minimumFlips(TreeNode* root, bool result) {
16        // Utility lambda function to perform a depth-first search on the tree.
17        // It returns a pair of integers representing the minimum flips needed to 
18        // make the subtree rooted at 'node' evaluate to false (first) and true (second).
19        function<pair<int, int>(TreeNode*)> dfs = [&](TreeNode* node) -> pair<int, int> {
20            // Base case: if the node is null, return maximum possible values
21            // since we can't flip a null node.
22            if (!node) {
23                return {INT_MAX, INT_MAX};
24            }
25            int value = node->val;
26            // If the value of the node is 0 or 1, it's a leaf node and we return 
27            // the cost to flip it to 0 (first) and to 1 (second), which is just one flip.
28            if (value < 2) {
29                return {value, value ^ 1};
30            }
31            // Recursively get the minimum flips for left and right subtrees.
32            auto [leftFlipsFalse, leftFlipsTrue] = dfs(node->left);
33            auto [rightFlipsFalse, rightFlipsTrue] = dfs(node->right);
34            int flipsToFalse = 0, flipsToTrue = 0;
35
36            // Based on the value of the node (operation type), combine the results from left
37            // and right subtrees to determine the minimum flips for current subtree.
38            if (value == 2) { // AND operation
39                flipsToFalse = leftFlipsFalse + rightFlipsFalse;
40                flipsToTrue = min({leftFlipsFalse + rightFlipsTrue, leftFlipsTrue + rightFlipsFalse, leftFlipsTrue + rightFlipsTrue});
41            } else if (value == 3) { // OR operation
42                flipsToFalse = min({leftFlipsFalse + rightFlipsFalse, leftFlipsFalse + rightFlipsTrue, leftFlipsTrue + rightFlipsFalse});
43                flipsToTrue = leftFlipsTrue + rightFlipsTrue;
44            } else if (value == 4) { // XOR operation
45                flipsToFalse = min(leftFlipsFalse + rightFlipsFalse, leftFlipsTrue + rightFlipsTrue);
46                flipsToTrue = min(leftFlipsFalse + rightFlipsTrue, leftFlipsTrue + rightFlipsFalse);
47            } else { // NOT operation (we assume that 'value' is either 0, 1, 2, 3, 4, or 5)
48                flipsToFalse = min(leftFlipsTrue, rightFlipsTrue);
49                flipsToTrue = min(leftFlipsFalse, rightFlipsFalse);
50            }
51            // Return the pair of flips for false and true.
52            return {flipsToFalse, flipsToTrue};
53        };
54
55        // Call the DFS function and get the minimum flips needed for false and true.
56        auto [flipsForFalse, flipsForTrue] = dfs(root);
57        // Return the corresponding flips based on the 'result' parameter.
58        return result ? flipsForTrue : flipsForFalse;
59    }
60};
61
1// The TreeNode class represents each node in the binary tree.
2class TreeNode {
3    val: number
4    left: TreeNode | null
5    right: TreeNode | null
6    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
7        this.val = (val === undefined ? 0 : val)
8        this.left = (left === undefined ? null : left)
9        this.right = (right === undefined ? null : right)
10    }
11}
12
13// The minimumFlips function calculates the minimum number of flips required
14// to make the output of the binary tree equal to the result boolean.
15// @param root - The root of the binary tree.
16// @param result - The expected result of the binary tree after performing flips.
17// @returns - the minimum number of flips needed.
18function minimumFlips(root: TreeNode | null, result: boolean): number {
19    // The dfs (Depth-First Search) function computes two values for each node:
20    // The minimum flips required to make the value of the subtree rooted at this node 0 and 1, respectively.
21    const dfs = (node: TreeNode | null): [number, number] => {
22        if (!node) {
23            // If the node is null, return maximum values as it contributes
24            // nothing to the count of flips.
25            return [Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER];
26        }
27      
28        const value = node.val;
29
30        // If the node is a leaf node or holds a value of 0 or 1, return the values
31        // itself and flip required to change it (0 becomes 1 and 1 becomes 0).
32        if (value < 2) {
33            return [value, value ^ 1];
34        }
35
36        // Otherwise, compute the flips for left and right subtrees.
37        const [leftFlipsToZero, leftFlipsToOne] = dfs(node.left);
38        const [rightFlipsToZero, rightFlipsToOne] = dfs(node.right);
39
40        // Calculate the flips based on the logical operation represented by the current node.
41        if (value === 2) {
42            // Logical AND
43            return [leftFlipsToZero + rightFlipsToZero, Math.min(leftFlipsToZero + rightFlipsToOne, leftFlipsToOne + rightFlipsToZero, leftFlipsToOne + rightFlipsToOne)];
44        }
45
46        if (value === 3) {
47            // Logical OR
48            return [Math.min(leftFlipsToZero + rightFlipsToZero, leftFlipsToZero + rightFlipsToOne, leftFlipsToOne + rightFlipsToZero), leftFlipsToOne + rightFlipsToOne];
49        }
50
51        if (value === 4) {
52            // Logical XOR
53            return [Math.min(leftFlipsToZero + rightFlipsToZero, leftFlipsToOne + rightFlipsToOne), Math.min(leftFlipsToZero + rightFlipsToOne, leftFlipsToOne + rightFlipsToZero)];
54        }
55
56        // Logical NAND
57        return [Math.min(leftFlipsToOne, rightFlipsToOne), Math.min(leftFlipsToZero, rightFlipsToZero)];
58    };
59
60    // Initial call to dfs function starting at the root,
61    // and return the required minimum flips based on the desired result.
62    return dfs(root)[result ? 1 : 0];
63}
64
Not Sure What to Study? Take the 2-min Quiz

Which of the following is a min heap?

Time and Space Complexity

The given code implements an algorithm to calculate the minimum number of flips necessary in a binary tree such that the value of the root node is equal to the desired result.

Time Complexity:

The time complexity of the algorithm is O(N), where N is the number of nodes in the binary tree. This is because we visit each node exactly once in a depth-first search (DFS) manner. For each node, we perform a constant-time operation regardless of its value, which either directly returns the values for leaves or calculates the minimum based on the values returned from the children for internal nodes.

Space Complexity:

The space complexity of the algorithm can be analyzed by considering the call stack for the recursive function dfs. In the worst-case scenario, the recursion depth is equal to the height of the tree. For a balanced binary tree, the height is O(log N), which would make the space complexity O(log N) due to the call stack. However, for a completely unbalanced tree (e.g., a linked list), the recursion could be as deep as O(N). Thus, the space complexity of the algorithm is O(H), where H is the height of the tree, and in the worst case, it is O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these properties could exist for a graph but not a tree?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«