Skip to main content
Talentd

Evaluate Boolean Binary Tree - Solution & Explanation

EasyTreeDepth-First SearchBinary Tree21 min readAsked at: Google
Practice this problem

Problem Statement

You are given the root of a full binary tree with the following properties:

  • Leaf nodes have either the value 0 or 1, where 0 represents False and 1 represents True.
  • Non-leaf nodes have either the value 2 or 3, where 2 represents the boolean OR and 3 represents the boolean AND.

The evaluation of a node is as follows:

  • If the node is a leaf node, the evaluation is the value of the node, i.e. True or False.
  • Otherwise, evaluate the node's two children and apply the boolean operation of its value with the children's evaluations.

Return the boolean result of evaluating the root node.

A full binary tree is a binary tree where each node has either 0 or 2 children.

A leaf node is a node that has zero children.

 

Example 1:

Input: root = [2,1,3,null,null,0,1]
Output: true
Explanation: The above diagram illustrates the evaluation process.
The AND node evaluates to False AND True = False.
The OR node evaluates to True OR False = True.
The root node evaluates to True, so we return true.

Example 2:

Input: root = [0]
Output: false
Explanation: The root node is a leaf node and it evaluates to false, so we return false.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 3
  • Every node has either 0 or 2 children.
  • Leaf nodes have a value of 0 or 1.
  • Non-leaf nodes have a value of 2 or 3.

Approach Overview

Problem Overview: You are given a binary tree where leaf nodes store boolean values (0 or 1) and internal nodes store operators. Value 2 represents OR and 3 represents AND. The task is to evaluate the tree and return the final boolean result at the root.

Approach 1: Recursive Depth-First Search (O(n) time, O(h) space)

The most natural solution uses recursion to evaluate the tree from the bottom up. Perform a DFS traversal on the binary tree. If a node is a leaf, simply return its boolean value. For internal nodes, recursively evaluate the left and right subtrees, then apply the operation stored in the current node. If the value is 2, compute left OR right. If the value is 3, compute left AND right. Each node is processed exactly once, giving O(n) time where n is the number of nodes. The recursion stack consumes O(h) space, where h is the tree height.

This approach mirrors how expression trees are normally evaluated. The recursion naturally propagates computed boolean values upward, which keeps the implementation concise and easy to reason about.

Approach 2: Iterative DFS Using Stack (O(n) time, O(h) space)

An iterative alternative replaces recursion with an explicit stack. Traverse the tree using a stack while simulating a postorder traversal. Push nodes while moving down the tree, and evaluate a node only after its children have been processed. Maintain a structure (such as a map or stack state) to store evaluated boolean results for child nodes. When processing an internal node, pop the results of its children and apply the operator: OR for value 2 and AND for value 3.

This method also touches each node once, so the runtime remains O(n). The stack stores at most the path from root to leaf, which requires O(h) space. The approach avoids recursion limits and gives more control over traversal order, which can be useful in environments where recursion depth is restricted.

Both solutions rely on standard tree traversal techniques and specifically a Depth-First Search pattern.

Recommended for interviews: The recursive DFS approach is what interviewers usually expect. It clearly demonstrates understanding of expression tree evaluation and DFS recursion. The iterative stack version shows deeper control over traversal mechanics and is useful when discussing recursion limits or stack simulation.

Approach 1: Recursive Approach

This approach uses recursion to evaluate the binary boolean tree. Starting from the root, recursively evaluate the left and right children of each node. If a node is a leaf, return its boolean value. If a node is non-leaf, apply the boolean operation defined by its value on its children's evaluations (OR for 2, AND for 3).

This C function implements the recursive evaluation of the binary tree. It first checks if the node is a leaf. If so, it returns the value directly. If not, it recursively evaluates the left and right subtrees, then applies the appropriate boolean operation ('OR' or 'AND') depending on the node's value.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the number of nodes, since we need to visit each node once.
Space Complexity: O(h) where h is the height of the tree, due to the recursion stack.

Try this approach in the editor →

Approach 2: Iterative Approach (Using Stack)

This method employs an iterative approach using a stack to emulate the recursive behavior. By performing a depth-first traversal, it uses a stack to track nodes and their processed children, evaluating each in line with the tree's logic operations.

This C solution uses a custom stack to simulate the recursion explicitly. Each node is processed with flags indicating the state of child evaluations, generating results from processed children before combining them under logical operations by parent nodes.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), as all nodes are processed.
Space Complexity: O(n), given the stack memory employment.

Try this approach in the editor →

Approach 3: Recursion

We can use recursion to solve this problem.

For the current node root:

  • If its left child is null, it means the current node is a leaf node. If the value of the current node is 1, then return true; otherwise, return false;
  • If the value of the current node is 2, then return the logical OR of the recursion results of its left and right children; otherwise, return the logical AND of the recursion results of its left and right children.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Approach

Time Complexity: O(n) where n is the number of nodes, since we need to visit each node once.
Space Complexity: O(h) where h is the height of the tree, due to the recursion stack.

Iterative Approach (Using Stack)

Time Complexity: O(n), as all nodes are processed.
Space Complexity: O(n), given the stack memory employment.

Recursion—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive DFSO(n)O(h)Best general solution. Clean implementation and natural for evaluating expression trees.
Iterative DFS (Stack)O(n)O(h)Useful when avoiding recursion or when stack control is required.

Video Solution

Evaluate Boolean Binary Tree - Leetcode 2331 - Python • NeetCodeIO • 9,518 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Evaluate Boolean Binary Tree easy or hard?
LeetCode classifies Evaluate Boolean Binary Tree as an Easy problem. The challenge mainly tests basic binary tree traversal and recursion. Once you recognize it as an expression tree evaluation, the implementation becomes straightforward.
Evaluate Boolean Binary Tree Python/Java solution
In Python or Java, implement a recursive function that returns the boolean value of a subtree. If the node is a leaf, return true for value 1 and false for value 0. Otherwise recursively evaluate the left and right children and apply OR (2) or AND (3) depending on the node value.
How to solve Evaluate Boolean Binary Tree in O(n)?
Use a Depth-First Search traversal. Recursively evaluate the left and right children of each internal node, then apply the operator stored at the node: OR for value 2 and AND for value 3. Since every node is processed once and each operation is constant time, the overall complexity remains O(n).
What is the best approach for Evaluate Boolean Binary Tree?
The recursive Depth-First Search approach is the most efficient and straightforward method. Traverse the binary tree, evaluate leaf nodes directly, and combine results using OR (2) or AND (3) operations at internal nodes. This processes each node once, resulting in O(n) time complexity and O(h) recursion stack space.
Is Evaluate Boolean Binary Tree asked at Google/Amazon/Meta?
Expression tree evaluation and DFS-based tree problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of boolean expression trees and binary tree evaluation are commonly used to test recursion and tree traversal skills.
What data structure is used in Evaluate Boolean Binary Tree?
The core data structure is a binary tree where nodes represent either boolean values or logical operators. The algorithm typically uses Depth-First Search with recursion or an explicit stack to traverse and evaluate the tree.
What is the time complexity of Evaluate Boolean Binary Tree?
The time complexity is O(n) because each node in the binary tree is visited exactly once during the traversal. The space complexity is O(h), where h is the height of the tree, due to the recursion stack or explicit stack used during DFS.

Ready to solve this problem?

Practice Evaluate Boolean Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check If Two Expression Trees are Equivalent

Next

Design an Expression Tree With Evaluate Function