2331. Evaluate Boolean Binary Tree
Problem Description
In this problem, we're given the root of a full binary tree representing a boolean expression. This tree has two types of nodes: leaf nodes and non-leaf nodes. Leaf nodes can only have a value of 0
(representing False
) or 1
(representing True
). Non-leaf nodes, on the other hand, hold a value of either 2
(representing the OR
operation) or 3
(representing the AND
operation). The task is to evaluate this tree according to the following rules:
- If the node is a leaf, its evaluation is based on its value (
True
for1
, andFalse
for0
). - For non-leaf nodes, you need to evaluate both of its children and then apply the node's operation (
OR
for2
,AND
for3
) to these evaluations.
The goal is to return the boolean result of this evaluation, starting at the root of the tree.
A full binary tree, by definition, is a binary tree where each node has exactly 0 or 2 children. A leaf node is a node without any children.
Flowchart Walkthrough
Let's employ the algorithm Flowchart to determine the best approach for Leetcode problem 2331, Evaluate Boolean Binary Tree. Here's a step-by-step analysis:
Is it a graph?
- Yes: A binary tree is a type of graph.
Is it a tree?
- Yes: Specifically, the problem is based on a binary tree structure.
Using the flowchart, when we ascertain that the structure is a tree, the subsequent decision step or node related to trees directly navigates us to use Depth-First Search (DFS) as the approach.
Conclusion: According to the flowchart, Depth-First Search (DFS) is recommended for tree-based problems like evaluating a Boolean binary tree.
Intuition
The solution to this problem lies in recursion, which matches the tree's structural nature. We will perform a post-order traversal to evaluate the tree ā this means we first evaluate the child nodes, and then we apply the operation specified by their parent node. Here's how we can think about our approach:
- If we reach a leaf node (a node with no children), we return its boolean value (
True
for1
,False
for0
). - If the node is not a leaf, it will have exactly two children because the tree is a full binary tree. We evaluate the left child and the right child first (recursively calling our function).
- Once both children are evaluated, we perform either an
OR
operation if the node's value is2
or anAND
operation if the node's value is3
. - We continue this process, working our way up the tree, until we reach the root.
- The result of evaluating the root node gives us the answer to the problem.
This recursive algorithm effectively simulates the process of evaluating a complex boolean expression, starting from the most basic sub-expressions (the leaf nodes) and combining them as specified by the connecting operation nodes.
Learn more about Tree, Depth-First Search and Binary Tree patterns.
Solution Approach
The solution is based on a simple recursive tree traversal algorithm. The evaluateTree
function is a recursive function that evaluates whether the boolean expression represented by the binary tree is True
or False
. Let's take a deeper dive into the implementation steps and algorithms used:
-
Base Case (Leaf Nodes): If we come across a leaf node (which has no children), the
evaluateTree
function simply returns the boolean equivalent of the node's value. In Python, the boolean valueTrue
corresponds to an integer value1
, andFalse
corresponds to0
. Hence,bool(root.val)
is sufficient to get the leaf node's boolean value. -
Recursive Case (Non-Leaf Nodes): For non-leaf nodes, since the tree is full, it is guaranteed that if a node is not a leaf, it will have both left and right children. We first recursively evaluate the result of the left child
self.evaluateTree(root.left)
and store this in the variablel
. Similarly, we evaluate the result of the right childself.evaluateTree(root.right)
and store it in the variabler
. -
Combining Results: Once we have the boolean evaluations of the left and the right children, we check the value of the current (parent) node:
- If the parent node's value is
2
, we perform anOR
operation on the results of the children. This is done byl or r
in Python. - If the parent node's value is
3
, we perform anAND
operation on the results of the children. This is done byl and r
in Python.
- If the parent node's value is
-
Termination and Return Value: The entire process recurses until the root node is evaluated. The result of evaluating the root node is then returned as the result of the boolean expression represented by the binary tree.
Here is a breakdown of the method in pseudocode:
def evaluateTree(node):
if node is a leaf:
return the boolean value of the leaf
else:
left_child_result = evaluateTree(node's left child)
right_child_result = evaluateTree(node's right child)
if node's value is OR:
return left_child_result OR right_child_result
else if node's value is AND:
return left_child_result AND right_child_result
The elegance of the recursive approach is in its direct mapping to the tree structure and the natural way it processes nodes according to the rules of boolean logic expression evaluation. At the end of the recursive calls, the evaluateTree
function gives us the final boolean evaluation for the entire tree starting from the root node. This aligns perfectly with the expected solution for the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate how the solution approach works.
Imagine a small binary tree representing a boolean expression, where leaf nodes are either 0
(False) or 1
(True), and non-leaf nodes are 2
(OR) or 3
(AND). Here is the structure of our example tree:
2 / \ 1 3 / \ 0 1
This tree represents the boolean expression (True OR (False AND True)).
Now, let's step through the algorithm:
-
We start at the root node, which is not a leaf and has a value of
2
, representing theOR
operation. Since this is not a leaf node, we need to evaluate its children. -
We evaluate the left child first. Here, the left child is a leaf with a value of
1
(True). According to our base case, we returnTrue
for this node. -
Next, we evaluate the right child, which is a non-leaf and has a value of
3
, representing theAND
operation. Since this is not a leaf node, we need to evaluate its children. -
We evaluate the left child of the
AND
node, which is a leaf with a value of0
(False). As per our base case, we returnFalse
for this node. -
Moving to the right child of the
AND
node, we find it is a leaf with a value of1
(True). We returnTrue
for this leaf. -
Now that we have the results of both children of the
AND
node (False and True), we apply theAND
operation. False AND True results inFalse
. -
Returning back to the root of the tree, we now have results from both children -
True
from the left andFalse
from the right (from theAND
operation). The root is anOR
node, so we apply theOR
operation to these results. -
True OR False gives us
True
. So, the final result of evaluating the entire tree isTrue
.
Hence, the boolean expression represented by the binary tree evaluates to True
. The recursive approach allowed us to break down the complex expression into simple operations that we could easily evaluate.
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 evaluateTree(self, root: Optional[TreeNode]) -> bool:
10 """
11 Evaluates the boolean value of a binary tree where leaves are 0 (False) or 1 (True),
12 and internal nodes are either 2 (OR) or 3 (AND).
13
14 :param root: The root node of the binary tree.
15 :return: The boolean result of evaluating the binary tree.
16 """
17 # If the current node is a leaf, return the boolean equivalent of its value
18 if root.left is None and root.right is None:
19 return bool(root.val)
20
21 # Recursively evaluate the left subtree
22 left_value = self.evaluateTree(root.left)
23 # Recursively evaluate the right subtree
24 right_value = self.evaluateTree(root.right)
25
26 # If the current node's value is 2, perform an OR operation; otherwise, perform an AND operation
27 if root.val == 2:
28 return left_value or right_value
29 else:
30 return left_value and right_value
31
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5 int val; // The value of the node
6 TreeNode left; // Reference to the left child
7 TreeNode right; // Reference to the right child
8
9 // Constructors
10 TreeNode() {}
11 TreeNode(int val) { this.val = val; }
12 TreeNode(int val, TreeNode left, TreeNode right) {
13 this.val = val;
14 this.left = left;
15 this.right = right;
16 }
17}
18
19class Solution {
20 /**
21 * Evaluates the boolean value of a binary tree with nodes labeled either
22 * 0 (false), 1 (true), 2 (OR), or 3 (AND). Leaves of the tree will always
23 * be labeled with 0 or 1. Nodes with values 2 or 3 represent the logical OR
24 * and AND operations, respectively.
25 *
26 * @param root The root node of the binary tree.
27 * @return The boolean result of evaluating the binary tree.
28 */
29 public boolean evaluateTree(TreeNode root) {
30 // Base case: If the node has no children, return true if it's value is 1, false otherwise.
31 if (root.left == null && root.right == null) {
32 return root.val == 1;
33 }
34
35 // Recursively evaluate the left and right subtrees.
36 boolean leftEvaluation = evaluateTree(root.left);
37 boolean rightEvaluation = evaluateTree(root.right);
38
39 // Determine the value of the current expression based on the current node's value
40 // If the node value is 2, perform logical OR, otherwise logical AND (as per the problem, value will be 3).
41 return (root.val == 2) ? leftEvaluation || rightEvaluation : leftEvaluation && rightEvaluation;
42 }
43}
44
1// Definition for a binary tree node.
2struct TreeNode {
3 int val; // Value of the node
4 TreeNode *left; // Pointer to the left child
5 TreeNode *right; // Pointer to the right child
6 // Constructor to initialize a node with no children
7 TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 // Constructor to initialize a node with a specific value and no children
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10 // Constructor to initialize a node with a specific value and specified children
11 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16 // Function to evaluate the value of a boolean binary tree
17 // based on the value of the root (0, 1, and 2 corresponding to false, true, and OR/AND operations)
18 bool evaluateTree(TreeNode* root) {
19 // If the root does not have a left child, it must be a leaf node (value 0 or 1)
20 if (!root->left) {
21 return root->val; // Return the value of the leaf node as the result
22 }
23 // Recursively evaluate the left subtree
24 bool leftResult = evaluateTree(root->left);
25 // Recursively evaluate the right subtree
26 bool rightResult = evaluateTree(root->right);
27 // If the root's value is 2, we perform an OR operation; otherwise, we perform an AND operation
28 return root->val == 2 ? (leftResult || rightResult) : (leftResult && rightResult);
29 }
30};
31
1// Definition for a binary tree node.
2interface TreeNode {
3 val: number;
4 left: TreeNode | null;
5 right: TreeNode | null;
6}
7
8/**
9 * Evaluates the boolean value of a binary logic tree where leaves represent
10 * boolean values and other nodes represent logical operators.
11 *
12 * @param {TreeNode | null} node - A node in a binary tree.
13 * @return {boolean} - The evaluated boolean value of the tree.
14 */
15function evaluateTree(node: TreeNode | null): boolean {
16 // Check if the node is null, which should not happen in a valid call
17 if (!node) {
18 throw new Error('Invalid node: Node cannot be null');
19 }
20
21 // If the node is a leaf node (i.e., both children are null), return true if it's value is 1, else false
22 if (node.left === null && node.right === null) {
23 return node.val === 1;
24 }
25
26 // Check the value of the node to determine the logical operator
27 if (node.val === 2) {
28 // Logical OR operator
29 return evaluateTree(node.left as TreeNode) || evaluateTree(node.right as TreeNode);
30 } else if (node.val === 3) {
31 // Logical AND operator
32 return evaluateTree(node.left as TreeNode) && evaluateTree(node.right as TreeNode);
33 }
34
35 throw new Error('Invalid node value: Node value must be either 1, 2, or 3');
36}
37
38// Note: The code assumes that the tree is a full binary tree and all non-leaf nodes have both left and right children.
39// It also assumes that the leaf nodes have the value 1 (true) or 0 (false), while other nodes have the value 2 (OR) or 3 (AND).
40
Time and Space Complexity
The time complexity of the provided code is O(n)
, where n
is the number of nodes in the binary tree. This is because the function evaluateTree
visits each node exactly once to perform the evaluation.
The space complexity is O(h)
, where h
is the height of the binary tree. This space is used by the call stack due to recursion. In the worst case of a skewed tree, where the tree is essentially a linked list, the height h
is n
, making the space complexity O(n)
. In the best case, with a balanced tree, the height h
would be log(n)
, resulting in a space complexity of O(log(n))
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a good use case for backtracking?
Recommended Readings
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
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
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
Want a Structured Path to Master System Design Too? Donāt Miss This!