Evaluate Boolean Binary Tree

Easy
1887.

Evaluate Boolean Binary Tree

Evaluate Boolean Binary Tree is an easy coding problem on depth-first search and trees, asked in Amazon and Google interviews.

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) or 1 (True).
  • A non-leaf node holds 2 (OR) or 3 (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 <= 1000
  • 0 <= Node.val <= 3
  • every node has 0 or 2 children
  • leaves hold 0 or 1; non-leaf nodes hold 2 or 3
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var evaluateTree = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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) or 1 (True).
  • A non-leaf node holds 2 (OR) or 3 (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 <= 1000
  • 0 <= Node.val <= 3
  • every node has 0 or 2 children
  • leaves hold 0 or 1; non-leaf nodes hold 2 or 3

Hints for Evaluate Boolean Binary Tree

  1. Hint 1

    A node's value depends only on its children's values — evaluate bottom-up.

  2. Hint 2

    A leaf answers directly: 1 is true, 0 is false.

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

  1. If the node holds 0 or 1, return false or true.
  2. Otherwise evaluate the left and right children.
  3. 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