Abstract / Summary

Given a boolean binary tree with leaves labeled true or false evaluate it to return true or false.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 82% (200k+ submissions).

Typical patterns to solve this problem:

• Binary Tree
• Depth First Search
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single public method evaluateTree. This method receives the root of a binary tree whose nodes encode boolean values and logical operators. The core of the algorithm is a nested helper function named deeper that recursively traverses the tree, evaluates leaf nodes as boolean constants, and combines the results of sub-trees using logical OR or AND depending on the node’s value. The final boolean result of the whole expression tree is returned to the caller.

Core Recursive Evaluation

The recursion is introduced with the inner function deeper. Its signature accepts a single node and returns a Python bool. The first code fragment shows the definition and the immediate return of the helper from evaluateTree.

def evaluateTree(self, root: Optional[TreeNode]) -> bool:
    def deeper(node):
        ...
    return deeper(root)

Handling Constant Leaves

Leaf nodes are identified by the values 0 and 1. The function returns False for 0 and True for 1. This direct mapping eliminates any further traversal when a leaf is encountered.

if node.val == 0:
    return False
if node.val == 1:
    return True

Processing Logical Operators

When the node’s value is neither 0 nor 1, it represents a logical operator. The code distinguishes two cases:

• Value 2 corresponds to logical OR. The function evaluates the left child, then the right child, and returns the disjunction.
• Any other value (specifically 3) corresponds to logical AND. The function evaluates both children and returns the conjunction.

if node.val == 2:
    return deeper(node.left) or deeper(node.right)
else:  # node.val == 3
    return deeper(node.left) and deeper(node.right)

The use of Python’s built-in or and and operators provides short-circuit behavior: evaluation stops as soon as the result is determined, which can avoid unnecessary recursive calls on the second child.

Edge-Case Handling

The algorithm gracefully manages several edge conditions without explicit checks:

• Single-node trees - When the root itself is a leaf (0 or 1), the recursion terminates immediately after the constant-leaf block, returning the appropriate boolean.
• Deeply nested expressions - The recursive structure naturally descends to any depth, evaluating each sub-expression in turn.
• Missing children - The code assumes that operator nodes (2 or 3) always have both left and right children, which aligns with the typical definition of a binary boolean expression tree. If a child were None, the recursive call would raise an exception, but within the intended problem constraints this situation does not arise.

Performance Optimizations

The implementation incorporates a few subtle optimizations that improve runtime efficiency:

• Early return for leaf values - By checking for 0 and 1 before any recursive calls, the function avoids unnecessary stack frames for leaf nodes.
• Short-circuit logical operators - Python’s or and and stop evaluating the right operand once the result is known. In an OR node, if the left subtree evaluates to True, the right subtree is never visited; similarly, an AND node skips the right subtree when the left evaluates to False. This can dramatically reduce the number of recursive invocations in trees where early termination is common.
• Local function scope - Defining deeper inside evaluateTree keeps the helper’s name resolution fast, as Python looks up the function in the local closure rather than at the class level.

These characteristics together ensure that the algorithm runs efficiently for typical binary expression trees, scaling proportionally with the number of nodes that must actually be visited.

Imagine a giant tree made of lights that goes way up into the sky. Each spot in the tree has a special number that tells the lights what to do. If a spot has a zero, the light stays off, and if it has a one, the light turns on.

Sometimes a spot has a two, which acts like a magical helper that says as long as one of its children lights up, the whole branch stays bright. If a spot has a three, it is a bit more strict and needs both of its children to be glowing for the branch to shine.

The code works by starting at the very top of the tree and looking down to see what each piece is doing. It travels down to the bottom where the simple zero and one lights are, then it carries that information back up. It keeps checking each spot to see if it needs a little bit of magic from the children below to decide if that part of the tree should sparkle or stay dark. It repeats this process until it has checked every single branch all the way to the top.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python	Java					C++			TS
	WalkCCC	Python	Java					C++
	leetcode.ca	Python	Java			Go		C++	C	Rust	TS
	Progiez	Python	Java					C++
github	chandansgowda	Python
	charles-wangkai		Java
	fartem			Ruby
	fsq							C++
	JoshCrozier				JS
	lkwq007	Python
	muhammadfarhankt					Go
	shreymehul						C#
	varunu28		Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
chandansgowda	Python
charles-wangkai	Java
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
muhammadfarhankt	Go
shreymehul	C#
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality