Evaluate Boolean Binary Tree — Problem & Solution
Evaluate Boolean Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Evaluate Boolean Binary Tree is an easy coding problem on depth-first search and trees, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a full binary tree (every node has either zero or two children) that encodes a boolean expression:
- A leaf holds
0(False) or1(True). - A non-leaf node holds
2(OR) or3(AND), applied to the values of its two children.
Return the boolean value of the root.
Example 1
Input: root = [2,1,3,null,null,0,1]
Output: true
Explanation: The AND node gives `False AND True = False`; the root gives `True OR False = True`.
Example 2
Input: root = [0]
Output: false
Explanation: The root is a leaf holding False.
Example 3
Input: root = [3,1,2,null,null,0,0]
Output: false
Explanation: `False OR False = False`, then `True AND False = False`.
Constraints
1 <= number of nodes <= 10000 <= Node.val <= 3every node has 0 or 2 childrenleaves hold 0 or 1; non-leaf nodes hold 2 or 3
Hints for Evaluate Boolean Binary Tree
Hint 1
A node's value depends only on its children's values — evaluate bottom-up.
Hint 2
A leaf answers directly: 1 is true, 0 is false.
Hint 3
For an internal node, evaluate both children recursively and combine them with OR (2) or AND (3).
How to solve Evaluate Boolean Binary Tree
The tree is an expression tree, so evaluating it is a post-order recursion: leaves are constants, internal nodes combine their children's results.
Approach
- If the node holds 0 or 1, return false or true.
- Otherwise evaluate the left and right children.
- Return their OR if the node holds 2, their AND if it holds 3.
Why it works
Each internal node's value is defined in terms of its children's values only, and the children are smaller subtrees, so structural induction gives the right value at every node, the root included.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion
Pitfalls
- Short-circuiting (
||,&&) is fine — the skipped subtree cannot change the result. - The tree is full, so an internal node always has both children; no null checks are needed beyond that guarantee.
Reference solution
Python
from typing import Optional
def evaluateTree(root: Optional[TreeNode]) -> bool:
if root.val < 2:
return root.val == 1
if root.val == 2:
return evaluateTree(root.left) or evaluateTree(root.right)
return evaluateTree(root.left) and evaluateTree(root.right)Java
public static boolean evaluateTree(TreeNode root) {
if (root.val < 2) return root.val == 1;
if (root.val == 2) return evaluateTree(root.left) || evaluateTree(root.right);
return evaluateTree(root.left) && evaluateTree(root.right);
}C++
bool evaluateTree(TreeNode* root) {
if (root->val < 2) return root->val == 1;
if (root->val == 2) return evaluateTree(root->left) || evaluateTree(root->right);
return evaluateTree(root->left) && evaluateTree(root->right);
}JavaScript
var evaluateTree = function(root) {
if (root.val < 2) return root.val === 1;
if (root.val === 2) return evaluateTree(root.left) || evaluateTree(root.right);
return evaluateTree(root.left) && evaluateTree(root.right);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals