Watch 10 video solutions for Evaluate Boolean Binary Tree, a easy level problem involving Tree, Depth-First Search, Binary Tree. This walkthrough by NeetCodeIO has 9,404 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |