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 for 1, and False for 0).
  • For non-leaf nodes, you need to evaluate both of its children and then apply the node's operation (OR for 2, AND for 3) 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.

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:

  1. If we reach a leaf node (a node with no children), we return its boolean value (True for 1, False for 0).
  2. 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).
  3. Once both children are evaluated, we perform either an OR operation if the node's value is 2 or an AND operation if the node's value is 3.
  4. We continue this process, working our way up the tree, until we reach the root.
  5. 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.

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:

  1. 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 value True corresponds to an integer value 1, and False corresponds to 0. Hence, bool(root.val) is sufficient to get the leaf node's boolean value.

  2. 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 variable l. Similarly, we evaluate the result of the right child self.evaluateTree(root.right) and store it in the variable r.

  3. 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 an OR operation on the results of the children. This is done by l or r in Python.
    • If the parent node's value is 3, we perform an AND operation on the results of the children. This is done by l and r in Python.
  4. 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:

1def evaluateTree(node):
2    if node is a leaf:
3        return the boolean value of the leaf
4    else:
5        left_child_result = evaluateTree(node's left child)
6        right_child_result = evaluateTree(node's right child)
7        if node's value is OR:
8            return left_child_result OR right_child_result
9        else if node's value is AND:
10            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.

💪
Level Up Your
Algo Skills

Example 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:

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

This tree represents the boolean expression (True OR (False AND True)).

Now, let's step through the algorithm:

  1. We start at the root node, which is not a leaf and has a value of 2, representing the OR operation. Since this is not a leaf node, we need to evaluate its children.

  2. 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 return True for this node.

  3. Next, we evaluate the right child, which is a non-leaf and has a value of 3, representing the AND operation. Since this is not a leaf node, we need to evaluate its children.

  4. We evaluate the left child of the AND node, which is a leaf with a value of 0 (False). As per our base case, we return False for this node.

  5. Moving to the right child of the AND node, we find it is a leaf with a value of 1 (True). We return True for this leaf.

  6. Now that we have the results of both children of the AND node (False and True), we apply the AND operation. False AND True results in False.

  7. Returning back to the root of the tree, we now have results from both children - True from the left and False from the right (from the AND operation). The root is an OR node, so we apply the OR operation to these results.

  8. True OR False gives us True. So, the final result of evaluating the entire tree is True.

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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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)).

😈
Become an
Algo Monster

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 👨‍🏫