Evaluate Boolean Binary Tree

easy binary tree recursion

Problem

You are given a full binary tree (every node has 0 or 2 children) whose leaves hold 0 (false) or 1 (true), and whose inner nodes hold 2 (OR) or 3 (AND). A leaf evaluates to its own boolean; an inner node evaluates by applying its operation to the evaluations of its two children. Return the boolean value of the root.

Inputroot = [2,1,3,null,null,0,1]

Outputtrue

The AND node gives false AND true = false; the OR root then gives true OR false = true.

tree (level-order: 0/1 leaves, 2=OR, 3=AND, null for gaps)

def evaluate_tree(root):
    if not root.left:                 # leaf node
        return root.val == 1
    left = evaluate_tree(root.left)
    right = evaluate_tree(root.right)
    if root.val == 2:                 # 2 means OR
        return left or right
    return left and right             # 3 means AND

function evaluateTree(root) {
  if (!root.left) {                  // leaf node
    return root.val === 1;
  }
  const left = evaluateTree(root.left);
  const right = evaluateTree(root.right);
  if (root.val === 2) return left || right;  // OR
  return left && right;                      // AND
}

public boolean evaluateTree(TreeNode root) {
    if (root.left == null) {           // leaf node
        return root.val == 1;
    }
    boolean left = evaluateTree(root.left);
    boolean right = evaluateTree(root.right);
    if (root.val == 2) return left || right;   // OR
    return left && right;                      // AND
}

bool evaluateTree(TreeNode* root) {
    if (!root->left) {                 // leaf node
        return root->val == 1;
    }
    bool left = evaluateTree(root->left);
    bool right = evaluateTree(root->right);
    if (root->val == 2) return left || right;  // OR
    return left && right;                      // AND
}

Explanation

The tree itself is the boolean expression: leaves are constants, inner nodes are operators. The value of any node depends only on the values of its children, so the natural strategy is a post-order traversal — fully evaluate both subtrees, then combine the two results at their parent.

The recursion has a tiny base case. Because the tree is full, a node missing a left child is guaranteed to be a leaf, so if not root.left is enough to detect one, and a leaf simply returns root.val == 1.

For an inner node we recurse into the left child, recurse into the right child, and then apply the node's operator: value 2 means OR (left or right) and value 3 means AND (left and right). The boolean bubbles up one level at a time until the root returns the final answer.

Walking the default example [2,1,3,null,null,0,1]: the root is OR with a left leaf 1 (true) and a right AND node. The AND node evaluates its leaves 0 (false) and 1 (true) and combines them: false AND true = false. Back at the root, true OR false = true, so the tree evaluates to true.

Every node is visited exactly once and each visit does constant work, giving O(n) time. The only extra memory is the recursion stack, which grows to the height of the tree: O(h), up to O(n) for a skewed full tree and O(log n) for a balanced one.

Time: O(n) Space: O(h)