Evaluate Boolean Binary Tree

Easy · Graphs · Explanation and code example

Iterative DFS

How it works

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.

Steps

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

Complexity

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

Things to watch for

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.

Python code example

from typing import Optional

# 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]

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        stack<TreeNode*> stk;
        unordered_map<TreeNode*, bool> value;
        stk.push(root);

        while (!stk.empty()) {
            TreeNode* node = stk.top();
            stk.pop();

            if (!node->left) {
                value[node] = node->val == 1;
            } else if (value.count(node->left)) {
                bool leftValue = value[node->left];
                bool rightValue = value[node->right];

                if (node->val == 2) {
                    value[node] = leftValue || rightValue;
                } else if (node->val == 3) {
                    value[node] = leftValue && rightValue;
                }
            } else {
                stk.push(node);
                stk.push(node->right);
                stk.push(node->left);
            }
        }

        return value[root];
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations