You are given the root of a full binary tree with the following properties:
0 or 1, where 0 represents False and 1 represents True.2 or 3, where 2 represents the boolean OR and 3 represents the boolean AND.The evaluation of a node is as follows:
True or False.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:
[1, 1000].0 <= Node.val <= 30 or 2 children.0 or 1.2 or 3.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.
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.
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.
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.
Time Complexity: O(n), as all nodes are processed.
Space Complexity: O(n), given the stack memory employment.
We can use recursion to solve this problem.
For the current node root:
1, then return true; otherwise, return false;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.
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n) where n is the number of nodes, since we need to visit each node once. |
| Iterative Approach (Using Stack) | Time Complexity: O(n), as all nodes are processed. |
| Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS | O(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. |
Evaluate Boolean Binary Tree - Leetcode 2331 - Python • NeetCodeIO • 9,404 views views
Watch 9 more video solutions →Practice Evaluate Boolean Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor