Minimum Flips In Binary Tree to Get Result
InformaticaThe problem
The root of a binary tree with the following attributes is provided to you:
-
False and true are represented by the values 0 and 1, respectively, for leaf nodes.
-
The boolean operations OR, AND, XOR, and NOT are represented by the values 2, 3, 4, and 5, respectively, for non-leaf nodes.
Additionally, a boolean result—the intended outcome of the root node evaluation—is provided to you.
The following is how a node is evaluated:
- The evaluation is the node's value, which can be either true or false if the node is a leaf node.
- If not, assess the node's offspring and use the boolean operation of its value in conjunction with the assessments of the offspring.
In a single action, you can flip a leaf node, making a true node false and a false node true.
Give back the bare **minimum **of steps required to ensure that the evaluation of root yields results. It can be demonstrated that a solution is always possible.
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.
Input : root = [2, 4, 3, 5, 1, 0, 0, 1] , result = false Output : 1 Explanation : We can flip the value of leaf node attached to node with value 5.
Input : root = [3,5,4,2,null,1,1,1,0], result = true **Output : **2 Explanation : We can flip the value of leaf node under node with value 2 from true to false. in 2nd operation we flip the leaf node under node with value 4 from true to false.
Input : root = [2, 4, 3, 5, 2, 0, 5, 1, null, 0, 1, null, null, 0], result = false
- 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.
cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
class Solution {
public:
int minimumFlips(TreeNode* root, bool result) {
//your code goes here
}
};java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int data;
* TreeNode left;
* TreeNode right;
* TreeNode(int val) { data = val; left = null, right = null }
* }
**/
class Solution {
public int minimumFlips(TreeNode root, boolean result) {
//your code goes here
}
}python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.data = val
# self.left = left
# self.right = right
class Solution:
def minimumFlips(self, root, result):
#your code goes herejavascript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null){
* this.data = val;
* this.left = null;
* this.right = null;
* }
* }
**/
class Solution {
minimumFlips(root, result) {
//your code goes here
}
}csharp
public class Solution {
public int MinimumFlips(TreeNode root, int result) {
//your code goes here
}
}go
func minimumFlips(root *TreeNode, result bool) int {
// Your code goes here
}Stuck? Show a way to structure it+
- 01Return minimum cost for both Boolean outcomes per node.
- 02Initialize leaves according to their current value and flip cost.
- 03Combine child outcome costs for the node operator.
- 04Also consider changing an operator if permitted.
- 05Read the requested root outcome.
Reference answer
Then expect these follow-ups
How would you handle ternary operators?
Tests: state design
How can you make recursion iterative?
Tests: postorder traversal
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question