Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Evaluate Boolean Binary Tree solution and explanation

EasyBinary TreeDepth-First SearchTree6 min read82.7% acceptanceUpdated 9 Apr 2026
Asked atGoogle
Practise Evaluate Boolean Binary Tree
14:55
Evaluate Boolean Binary Tree - Leetcode 2331 - PythonNeetCodeIO · 14:55 · 9K viewsWatch on YouTube
9 more videos on this problem
  1. Evaluate Boolean Binary Tree - Leetcode 2331 - PythonNeetCodeIO · 14:55 · 9K views
  2. Evaluate Boolean Binary Tree | Simple Story To Code | Leetcode 2331 | codestorywithMIKcodestorywithMIK · 8:59 · 4K views
  3. 2331. Evaluate Boolean Binary Tree | leetcode daily challenge | DSA | HindiShashCode · 10:39 · 913 views
  4. 2331. Evaluate Boolean Binary Tree (Leetcode Easy)Programming Live with Larry · 5:04 · 753 views
  5. 2331 Evaluate Boolean Binary Tree | Leet Code #2331 | Coding in Telugu | LVS logics | ProblemSolvingLVS Logics · 8:57 · 459 views
  6. Evaluate Boolean Binary Tree | Leetcode 2331 | Amazon Google Facebook interview questionSuper Lazy Coder · 6:21 · 271 views
  7. Daily Leetcode #1507: May 16, 2024 - 2331. Evaluate Boolean Binary TreeProgramming Live with Larry · 7:15 · 237 views
  8. LeetCode 2331 | Evaluate Boolean Binary Tree | Recursion | JavaSleepy Cracker · 2:32 · 219 views
  9. Evaluate Boolean Binary Tree - LeetCode 2331 - Java Solutionalgobest - Computer Science · 3:31 · 146 views
  10. C++ Walkthrough - LeetCode#2331 - Evaluate Boolean Binary TreeJoshProgramin · 8:24 · 135 views

The problem

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

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def evaluateTree(self, root: TreeNode) -> bool:
        if not root.left and not root.right:
            return root.val == 1
        left = self.evaluateTree(root.left)
        right = self.evaluateTree(root.right)
        return (left or right) if root.val == 2 else (left and right)
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public boolean evaluateTree(TreeNode root) {
        if (root.left == null && root.right == null) {
            return root.val == 1;
        }
        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        return root.val == 2 ? left || right : left && right;
    }
}
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool evaluateTree(TreeNode* root) {
    if (!root->left && !root->right)
        return root->val;
    bool left = evaluateTree(root->left);
    bool right = evaluateTree(root->right);
    return root->val == 2 ? left || right : left && right;
}
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var evaluateTree = function(root) {
    if (!root.left && !root.right)
        return root.val === 1;
    let left = evaluateTree(root.left);
    let right = evaluateTree(root.right);
    return root.val === 2 ? left || right : left && right;
};
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

bool evaluateTree(struct TreeNode* root) {
    if (root->val < 2)
        return root->val;
    bool left = evaluateTree(root->left);
    bool right = evaluateTree(root->right);
    return root->val == 2 ? left || right : left && right;
}
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public bool EvaluateTree(TreeNode root) {
        if (root.left == null && root.right == null) {
            return root.val == 1;
        }
        bool left = EvaluateTree(root.left);
        bool right = EvaluateTree(root.right);
        return root.val == 2 ? left || right : left && right;
    }
}

Python version follows the recursive evaluation pattern where recursive calls are used for children evaluations and logical operations are applied based on the current node's value.

Complexity

Time Complexity: O(n) since every node requires visitation.
Space Complexity: O(h) due to recursion stack proportional to tree height.

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.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def evaluateTree(self, root: TreeNode) -> bool:
        stack = [(root, False)]
        while stack:
            node, processed = stack.pop()
            if node.left is None and node.right is None:
                node.val = bool(node.val)
            elif not processed:
                stack.append((node, True))
                if node.right:
                    stack.append((node.right, False))
                if node.left:
                    stack.append((node.left, False))
            else:
                left_val = node.left.val if node.left else False
                right_val = node.right.val if node.right else False
                node.val = (left_val or right_val) if node.val == 2 else (left_val and right_val)
        return bool(root.val)
import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public boolean evaluateTree(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) return false;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.left == null && node.right == null) {
                node.val = node.val == 1 ? 1 : 0;
            } else {
                if (node.left != null) stack.push(node.left);
                if (node.right != null) stack.push(node.right);

                int leftVal = node.left != null ? node.left.val : 0;
                int rightVal = node.right != null ? node.right.val : 0;
                if (node.val == 2) { // OR operation
                    node.val = leftVal == 1 || rightVal == 1 ? 1 : 0;
                } else if (node.val == 3) { // AND operation
                    node.val = leftVal == 1 && rightVal == 1 ? 1 : 0;
                }
            }
        }
        return root.val == 1;
    }
}
#include <stack>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool evaluateTree(TreeNode* root) {
    std::stack<std::pair<TreeNode*, bool>> s;
    s.push({root, false});
    while (!s.empty()) {
        auto [node, processed] = s.top();
        s.pop();
        if (!node->left && !node->right) {
            node->val = node->val == 1;
            continue;
        }
        if (!processed) {
            s.push({node, true});
            if (node->right) s.push({node->right, false});
            if (node->left) s.push({node->left, false});
        } else {
            bool left = node->left->val;
            bool right = node->right->val;
            node->val = node->val == 2 ? (left || right) : (left && right);
        }
    }
    return root->val;
}
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val);
    this.left = (left===undefined ? null : left);
    this.right = (right===undefined ? null : right);
}

var evaluateTree = function(root) {
    let stack = [{ node: root, processed: false }];
    while (stack.length) {
        let { node, processed } = stack.pop();
        if (!node.left && !node.right) {
            node.val = node.val === 1;
        } else if (!processed) {
            stack.push({ node, processed: true });
            if (node.right) stack.push({ node: node.right, processed: false });
            if (node.left) stack.push({ node: node.left, processed: false });
        } else {
            let leftVal = node.left ? node.left.val : 0;
            let rightVal = node.right ? node.right.val : 0;
            node.val = node.val === 2 ? (leftVal || rightVal) : (leftVal && rightVal);
        }
    }
    return root.val === 1;
};
#include <stdbool.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct StackNode {
    struct TreeNode* treeNode;
    bool leftEvaluated;
    bool rightEvaluated;
    struct StackNode* next;
};

void push(struct StackNode** top, struct TreeNode* node) {
    struct StackNode* newStackNode = (struct StackNode*)malloc(sizeof(struct StackNode));
    newStackNode->treeNode = node;
    newStackNode->leftEvaluated = false;
    newStackNode->rightEvaluated = false;
    newStackNode->next = (*top);
    (*top) = newStackNode;
}

struct StackNode* pop(struct StackNode** top) {
    if (*top == NULL) return NULL;
    struct StackNode* temp = *top;
    *top = (*top)->next;
    return temp;
}

bool evaluateTree(struct TreeNode* root) {
    struct StackNode* stack = NULL;
    bool result = false;
    if (root == NULL) return result;
    push(&stack, root);
    while (stack) {
        struct StackNode* topNode = stack;
        struct TreeNode* current = topNode->treeNode;
        if (current->left == NULL && current->right == NULL) {
            result = current->val == 1;
            pop(&stack);
        } else if (!topNode->leftEvaluated) {
            if (current->left) push(&stack, current->left);
            topNode->leftEvaluated = true;
        } else if (!topNode->rightEvaluated) {
            bool leftResult = result;
            if (current->right) push(&stack, current->right);
            topNode->rightEvaluated = true;
            result = current->val == 2 ? leftResult || result : leftResult && result;
        } else {
            pop(&stack);
        }
    }
    return result;
}
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public bool EvaluateTree(TreeNode root) {
        if (root == null) return false;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(root);
        while (stack.Count > 0) {
            TreeNode node = stack.Pop();
            if (node.left == null && node.right == null) {
                node.val = node.val == 1 ? 1 : 0;
                continue;
            }
            if (node.left != null) stack.Push(node.left);
            if (node.right != null) stack.Push(node.right);
            int leftVal = node.left != null ? node.left.val : 0;
            int rightVal = node.right != null ? node.right.val : 0;
            if (node.val == 2) { // OR
                node.val = (leftVal == 1 || rightVal == 1) ? 1 : 0;
            } else if (node.val == 3) { // AND
                node.val = (leftVal == 1 && rightVal == 1) ? 1 : 0;
            }
        }
        return root.val == 1;
    }
}

The Python solution opts for iteration via a stack implemented as a list, managing nodes with a tuple indicating processing state. Child node values are processed first before handling parent's logical operation.

Complexity

Time Complexity: O(n), due to comprehensive node processing.
Space Complexity: O(n), as nodes are preserved on stack.

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.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function evaluateTree(root: TreeNode | null): boolean {
    const { val, left, right } = root;
    if (left === null) {
        return val === 1;
    }
    if (val === 2) {
        return evaluateTree(left) || evaluateTree(right);
    }
    return evaluateTree(left) && evaluateTree(right);
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func evaluateTree(root *TreeNode) bool {
	if root.Left == nil {
		return root.Val == 1
	}
	if root.Val == 2 {
		return evaluateTree(root.Left) || evaluateTree(root.Right)
	} else {
		return evaluateTree(root.Left) && evaluateTree(root.Right)
	}
}
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    pub fn evaluate_tree(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        match root {
            Some(node) => {
                let node = node.borrow();
                if node.left.is_none() {
                    return node.val == 1;
                }
                if node.val == 2 {
                    return Self::evaluate_tree(node.left.clone())
                        || Self::evaluate_tree(node.right.clone());
                }
                Self::evaluate_tree(node.left.clone()) && Self::evaluate_tree(node.right.clone())
            }
            None => false,
        }
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Recursive Approach

Time Complexity: O(n) since every node requires visitation.
Space Complexity: O(h) due to recursion stack proportional to tree height.

Iterative Approach (Using Stack)

Time Complexity: O(n), due to comprehensive node processing.
Space Complexity: O(n), as nodes are preserved on stack.

Recursion–

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.

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.

Comments

Next problem · similarCheck If Two Expression Trees are EquivalentMedium
Now write it yourselfClose this page and solve Evaluate Boolean Binary Tree in the editor, without looking.
Practise Evaluate Boolean Binary Tree