2331. Evaluate Boolean Binary Tree - Explanation

Problem Link

1. Depth First Search

Intuition

This is a classic tree evaluation problem. Leaf nodes hold boolean values (0 or 1), while internal nodes represent OR (2) or AND (3) operations. We recursively evaluate each subtree: leaf nodes return their value directly, and internal nodes combine their children's results using the appropriate operator. The tree structure naturally maps to the recursive call stack.

Algorithm

1. If the node has no left child (it's a leaf), return true if val == 1, else false.
2. Recursively evaluate the left and right subtrees.
3. If val == 2 (OR), return left_result OR right_result.
4. If val == 3 (AND), return left_result AND right_result.

# 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 not root.left:
            return root.val == 1

        if root.val == 2:
            return self.evaluateTree(root.left) or self.evaluateTree(root.right)

        if root.val == 3:
            return self.evaluateTree(root.left) and self.evaluateTree(root.right)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$ for recursion stack.

---

2. Iterative DFS

Intuition

We can avoid recursion by using an explicit stack and a hash map to store computed values. The key challenge is handling the post-order nature of evaluation: a node can only be evaluated after both its children are processed. We achieve this by pushing nodes back onto the stack if their children haven't been evaluated yet, effectively simulating the recursive call stack.

Algorithm

1. Initialize a stack with the root and a hash map value to store results.
2. While the stack is non-empty:
   • Pop a node.
   • If it's a leaf, store its boolean value in value.
   • If both children are already in value, compute and store the result.
   • Otherwise, push the node back, then push both children (so they get processed first).
3. Return value[root].

# 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:
        stack = [root]
        value = {} # map (node -> value)

        while stack:
            node = stack.pop()

            if not node.left:
                value[node] = node.val == 1
            elif node.left in value:
                if node.val == 2:
                    value[node] = value[node.left] or value[node.right]
                if node.val == 3:
                    value[node] = value[node.left] and value[node.right]
            else:
                stack.extend([node, node.left, node.right])

        return value[root]

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

Common Pitfalls

Confusing Leaf Detection with Null Check

To identify a leaf node, check if root.left is null (since the problem guarantees full binary tree, both children are null or both exist). A common mistake is checking root == null instead, which would return incorrect results for the recursive base case.

Mixing Up Operator Values

The problem uses val == 2 for OR and val == 3 for AND. Swapping these operators or using incorrect comparison values produces wrong boolean results. Always double-check the operator mapping: 0/1 for leaf values, 2 for OR, 3 for AND.