Evaluate Boolean Binary Tree

Evaluate Boolean Binary Tree

What is this problem about?

The Evaluate Boolean Binary Tree interview question involves a special kind of binary tree. Leaf nodes contain boolean values (0 for False, 1 for True). Non-leaf nodes contain boolean operators (2 for OR, 3 for AND). You need to recursively evaluate the tree and return the boolean result of the entire expression rooted at the top.

Why is this asked in interviews?

This is a popular "Easy" level Tree interview pattern used by Amazon and Google. it tests your fundamental understanding of recursion and tree traversal. It’s an excellent problem for beginners to practice the post-order traversal logic (evaluating children before the parent).

Algorithmic pattern used

This problem is a direct application of Depth-First Search (DFS), specifically Post-Order Traversal.

1. Base Case: If the node is a leaf, return its boolean value.
2. Recursive Step:
   • Evaluate the left child.
   • Evaluate the right child.
   • Apply the current node's operator (AND or OR) to the results of the children.
3. Return the final result.

Example explanation

Tree: [OR, True, AND, null, null, False, True]

1. Root is OR.
2. Left child is True.
3. Right child is an AND node.
   • Evaluate AND: its children are False and True. False AND True = False.
4. Now back at the root: True OR False = True. The entire tree evaluates to True.

Common mistakes candidates make

• Incorrect Base Case: Not checking if a node is a leaf before trying to access its operator.
• Short-circuiting logic: While not a "mistake" in logic, forgetting that boolean operators in many languages (like || and &&) already handle short-circuiting can lead to slightly more code than necessary.
• Traversing Nulls: Trying to evaluate children of a leaf node.

Interview preparation tip

Always remember: Post-order traversal is the standard for "evaluation" problems (like math expressions or boolean trees) because the parent's value depends entirely on the already-computed values of its children.