LeetCode 2331 - Evaluate Boolean Binary Tree

The problem asks us to evaluate a full binary tree where each node represents either a boolean value or a boolean operation. Leaf nodes have values 0 (False) or 1 (True). Non-leaf nodes have values 2 (OR) or 3 (AND).

leetcodeeasytreedepth-first-searchbinary-tree

LeetCode Problem 2331

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to evaluate a full binary tree where each node represents either a boolean value or a boolean operation. Leaf nodes have values 0 (False) or 1 (True). Non-leaf nodes have values 2 (OR) or 3 (AND). The goal is to compute the boolean value at the root by recursively evaluating all children according to the rules of the tree.

The input is the root of the binary tree, where each node is an instance of TreeNode. The output is a single boolean value, True or False, representing the evaluation of the entire tree. A full binary tree constraint ensures that each node has either 0 or 2 children, so we do not need to handle nodes with only one child. The number of nodes is up to 1000, which allows for recursive traversal without worrying about stack overflow in typical environments.

Important edge cases include a tree with a single leaf node, all nodes evaluating to True, or all nodes evaluating to False. The tree is guaranteed to follow the constraints, so we do not need to handle invalid node values or non-binary structures.

Approaches

The brute-force approach involves recursively evaluating the tree exactly as described in the problem statement. Starting from the root, we check if the node is a leaf. If so, we return its boolean value. Otherwise, we recursively evaluate the left and right children, then apply the operation at the current node (OR or AND). This approach works correctly because it follows the tree's boolean evaluation rules directly. For the given constraints, this is already efficient, as each node is visited exactly once.

The key insight is that the recursive approach is optimal due to the tree's structure. Each node is visited exactly once, and no additional data structures are required beyond the recursion stack. There is no need for memoization or dynamic programming because there is no repeated subproblem evaluation in a tree.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(h) Recursively evaluate each node; h is the height of the tree
Optimal O(n) O(h) Same as brute-force; optimal for full binary trees

Algorithm Walkthrough

  1. Start at the root node. Check if the node is a leaf by verifying if both left and right children are None.
  2. If the node is a leaf, return True if node.val == 1 and False if node.val == 0. This handles the base case.
  3. If the node is not a leaf, recursively evaluate the left child by calling the function on node.left.
  4. Similarly, recursively evaluate the right child by calling the function on node.right.
  5. Once both children have been evaluated, check the value of the current node. If it is 2, perform a boolean OR on the two child values. If it is 3, perform a boolean AND on the two child values.
  6. Return the result of the operation back to the parent call.
  7. Repeat steps 1-6 until the root node has been evaluated, at which point the function returns the final boolean value.

Why it works: This algorithm works because it respects the recursive structure of the tree. Each node’s value is correctly computed based on its children, and leaf nodes serve as the base case. The recursive evaluation guarantees that every subtree is evaluated before the parent node applies its operation, ensuring correctness.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def evaluateTree(self, root: Optional[TreeNode]) -> bool:
        if root.left is None and root.right is None:
            return root.val == 1
        
        left_val = self.evaluateTree(root.left)
        right_val = self.evaluateTree(root.right)
        
        if root.val == 2:
            return left_val or right_val
        elif root.val == 3:
            return left_val and right_val

The implementation follows the algorithm exactly. The base case checks if the node is a leaf and returns the corresponding boolean. For non-leaf nodes, the function recursively evaluates left and right subtrees, then applies the appropriate boolean operation based on the node value.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func evaluateTree(root *TreeNode) bool {
    if root.Left == nil && root.Right == nil {
        return root.Val == 1
    }
    
    leftVal := evaluateTree(root.Left)
    rightVal := evaluateTree(root.Right)
    
    if root.Val == 2 {
        return leftVal || rightVal
    }
    return leftVal && rightVal
}

In Go, we follow the same logic. We check if a node is a leaf and return the boolean value. For non-leaf nodes, we recursively evaluate both children and apply the OR or AND operation. Go’s strict typing requires explicit boolean comparisons (root.Val == 1).

Worked Examples

Example 1

Input tree: [2,1,3,null,null,0,1]

Step-by-step evaluation:

  1. Root is 2 (OR). Evaluate left and right children.
  2. Left child is 1 (leaf) → evaluates to True.
  3. Right child is 3 (AND). Evaluate its children.
  4. Right-left child is 0 (leaf) → evaluates to False.
  5. Right-right child is 1 (leaf) → evaluates to True.
  6. Right node 3 → AND of False and True = False.
  7. Root 2 → OR of True and False = True.

Output: True.

Example 2

Input tree: [0]

  1. Root is 0 (leaf) → evaluates to False.

Output: False.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited exactly once.
Space O(h) Recursion stack uses space proportional to the height of the tree; h ≤ n in worst case.

The time complexity is optimal because we cannot avoid visiting all nodes in a tree. The space complexity is determined by the recursion stack, which is proportional to the height of the tree.

Test Cases

# Single leaf node, evaluates to False
assert Solution().evaluateTree(TreeNode(0)) == False

# Single leaf node, evaluates to True
assert Solution().evaluateTree(TreeNode(1)) == True

# OR root with True and False children
root = TreeNode(2, TreeNode(1), TreeNode(0))
assert Solution().evaluateTree(root) == True

# AND root with True and False children
root = TreeNode(3, TreeNode(1), TreeNode(0))
assert Solution().evaluateTree(root) == False

# Nested operations
root = TreeNode(2, TreeNode(1), TreeNode(3, TreeNode(0), TreeNode(1)))
assert Solution().evaluateTree(root) == True

# All leaves True with AND root
root = TreeNode(3, TreeNode(1), TreeNode(1))
assert Solution().evaluateTree(root) == True
Test Why
Single leaf 0 Tests base case evaluating to False
Single leaf 1 Tests base case evaluating to True
OR root True/False Tests OR operation
AND root True/False Tests AND operation
Nested tree Tests recursive evaluation correctness
All leaves True Ensures AND of all True works

Edge Cases

One important edge case is a tree with a single node. The implementation handles this by checking if the node is a leaf. Another edge case is when all leaf nodes evaluate to True or False, which tests that the boolean operations propagate correctly through AND and OR nodes. A third edge case is when the tree is heavily unbalanced, such as a degenerate tree (linked-list shape); the recursive solution still handles this correctly, but the recursion depth will equal the number of nodes, which is within constraints.

Overall, the recursive evaluation guarantees correctness and naturally handles all these edge cases.