#2331

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Evaluate Boolean Binary Tree

Determine the boolean outcome of a full binary tree by evaluating leaf and internal nodes using depth-first traversal.

Problem Statement

You are given a full binary tree where each node has either 0 or 2 children. Leaf nodes contain a boolean value of 0 (false) or 1 (true), while non-leaf nodes are operators: 2 represents an OR node and 3 represents an AND node. The goal is to determine the boolean result of evaluating the root based on these values.

Evaluation rules require computing leaf values directly and applying the logical operator at each non-leaf node to its children. Use post-order traversal to ensure child nodes are evaluated before combining their results. Return the final boolean value from the root node after all evaluations.

Examples

Example 1

Input: root = [2,1,3,null,null,0,1]

Output: true

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

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.

Solution Approach

Post-order Depth-First Traversal

Traverse the tree in post-order so that both children of a node are evaluated before computing the node's value. This ensures correct logical computation for AND and OR nodes.

Leaf Node Handling

Return the boolean value directly for leaf nodes. Leaves have values 0 or 1, representing false and true, which act as the base case for recursive evaluation.

Evaluate Non-Leaf Nodes

For nodes with value 2 or 3, compute the logical OR or AND of the child results. Value 2 corresponds to OR, 3 corresponds to AND. Combine child evaluations and propagate upward to the root.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Each node is visited once, giving O(n) time complexity, and the recursion stack can reach the height of the tree, giving O(n) space in the worst case for a skewed full binary tree.

What Interviewers Usually Probe

Expect recognition of post-order DFS to evaluate operators correctly.
Look for handling leaf nodes as base cases in recursion.
Check if candidate propagates boolean results correctly through non-leaf nodes.

Common Pitfalls or Variants

Common pitfalls

Attempting to evaluate parent nodes before children leads to incorrect boolean results.
Misinterpreting the node values: 2 is OR, 3 is AND, not the reverse.
Forgetting that leaf nodes return their value directly can cause unnecessary recursion or errors.

Follow-up variants

Tree with larger values or custom operators beyond AND/OR requires mapping logic accordingly.
Sparse binary tree with some missing nodes changes traversal approach and evaluation assumptions.
Binary tree where leaves can have more than two boolean outcomes would require adjusting leaf handling logic.

FAQ

What is the simplest approach to evaluate a boolean binary tree?

Use a post-order depth-first traversal, compute leaf values directly, and apply logical operations at non-leaf nodes.

How are node values interpreted in this problem?

Leaf nodes: 0 = false, 1 = true. Non-leaf nodes: 2 = OR, 3 = AND.

Can this approach handle any binary tree?

It specifically works for full binary trees with 0 or 2 children per node. Sparse or irregular trees need adjustments.

What is the time complexity of evaluating the boolean binary tree?

Each node is visited once, so the time complexity is O(n), with n being the number of nodes.

Why use post-order traversal for Evaluate Boolean Binary Tree?

Post-order ensures that child nodes are evaluated before their parent, which is necessary to correctly compute AND and OR results at non-leaf nodes.

terminal

Solution

Solution 1: Recursion

We can use recursion to solve this problem.

1

2

3

4

5

6

7

8

9

10

11

12

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> bool:
        if root.left is None:
            return bool(root.val)
        op = or_ if root.val == 2 else and_
        return op(self.evaluateTree(root.left), self.evaluateTree(root.right))

Continue Practicing

#2385 amount of time for binary tree to be infected #2265 count nodes equal to average of subtree #2415 reverse odd levels of binary tree