Evaluate Boolean Binary Tree

Easy

#2123Time: O(N), where N is the number of nodes in the tree. Each node is pushed onto the stack and processed a constant number of times.Space: O(N). The `evaluated` map stores a result for every node in the tree, leading to O(N) space. The stack also contributes up to O(H) space, where H is the tree height, but this is dominated by the map's space usage.

Algorithms

Depth-First Search

Data structures

Tree Binary Tree

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach avoids recursion by using a stack to manually manage the traversal of the tree in a post-order fashion. A map is used to store the evaluated boolean results of the subtrees, so we know when a parent node's children have been processed and it's ready for evaluation.

Algorithm

Initialize a stack and push the root node.
Initialize a HashMap<TreeNode, Boolean> named evaluated to store the results of evaluated subtrees.
Loop while the stack is not empty:
- a. Peek at the top node, node.
- b. If node is a leaf, pop it, store its boolean value (node.val == 1) in evaluated, and continue.
- c. Check if both of node's children are present as keys in the evaluated map.
- d. If yes, pop node, retrieve the children's results from the map, compute node's result, and store it in the evaluated map.
- e. If no, push the right child (if not evaluated) and then the left child (if not evaluated) onto the stack to ensure they are processed first.
After the loop terminates, the result for the root node will be in the evaluated map. Return evaluated.get(root).

Walkthrough

The algorithm simulates a post-order traversal, which is necessary because a parent node's value can only be computed after its children's values are known. We use a stack for the traversal and a HashMap called evaluated to store the boolean result for any node that has been computed.

The main loop continues as long as the stack is not empty. In each iteration, we look at the node at the top of the stack (peek()).

If the node is a leaf, we can evaluate it immediately (true for value 1, false for 0), store the result in our evaluated map, and pop the node from the stack.
If the node is an internal node, we check if both its children have already been evaluated by looking them up in the evaluated map.
- If both children are in the map, we can evaluate the current node. We pop it from the stack, retrieve the children's boolean values from the map, apply the OR (value 2) or AND (value 3) operation, and store the result for the current node in the evaluated map.
- If either child has not been evaluated yet, we push the unevaluated children onto the stack (right child first, then left child) so they will be processed before the current node.

The process continues until the root node is evaluated. The final answer is the value associated with the root in the evaluated map.

1import java.util.Stack;2import java.util.Map;3import java.util.HashMap;4 5/**6 * Definition for a binary tree node.7 * public class TreeNode {8 *     int val;9 *     TreeNode left;10 *     TreeNode right;11 *     TreeNode() {}12 *     TreeNode(int val) { this.val = val; }13 *     TreeNode(int val, TreeNode left, TreeNode right) {14 *         this.val = val;15 *         this.left = left;16 *         this.right = right;17 *     }18 * }19 */20class Solution {21    public boolean evaluateTree(TreeNode root) {22        Stack<TreeNode> stack = new Stack<>();23        stack.push(root);24        Map<TreeNode, Boolean> evaluated = new HashMap<>();25 26        while (!stack.isEmpty()) {27            TreeNode node = stack.peek();28 29            // Case 1: Node is a leaf30            if (node.left == null && node.right == null) {31                stack.pop();32                evaluated.put(node, node.val == 1);33                continue;34            }35 36            // Check if children have been evaluated37            boolean leftChildEvaluated = evaluated.containsKey(node.left);38            boolean rightChildEvaluated = evaluated.containsKey(node.right);39 40            // Case 2: Children have been evaluated, so evaluate the current node41            if (leftChildEvaluated && rightChildEvaluated) {42                stack.pop();43                boolean leftVal = evaluated.get(node.left);44                boolean rightVal = evaluated.get(node.right);45                if (node.val == 2) { // OR46                    evaluated.put(node, leftVal || rightVal);47                } else { // AND (val == 3)48                    evaluated.put(node, leftVal && rightVal);49                }50            } else {51                // Case 3: Children not yet evaluated, push them to the stack52                if (!rightChildEvaluated) {53                    stack.push(node.right);54                }55                if (!leftChildEvaluated) {56                    stack.push(node.left);57                }58            }59        }60        return evaluated.get(root);61    }62}

Complexity

Time

O(N), where N is the number of nodes in the tree. Each node is pushed onto the stack and processed a constant number of times.

Space

O(N). The `evaluated` map stores a result for every node in the tree, leading to O(N) space. The stack also contributes up to O(H) space, where H is the tree height, but this is dominated by the map's space usage.

Trade-offs

Pros

Avoids recursion, preventing potential stack overflow errors on extremely deep trees.
Can be more performant in some environments by avoiding the overhead of recursive function calls.

Cons

More complex to implement and reason about compared to the recursive solution.
Requires O(N) auxiliary space for the map, which is less space-efficient than the recursive approach's O(H) space.

This is the most natural and elegant approach for this problem. Since the evaluation of any non-leaf node depends on the evaluation of its children, a post-order traversal is a perfect fit. We recursively evaluate the left and right subtrees and then combine their results at the parent node.

Algorithm

Define a recursive function evaluateTree(node).
Base Case: If node is a leaf (node.left == null), return true if node.val == 1, else false.
Recursive Step:
- a. Call evaluateTree(node.left) to get the result of the left subtree.
- b. Call evaluateTree(node.right) to get the result of the right subtree.
- c. If node.val is 2 (OR), return the logical OR of the children's results.
- d. If node.val is 3 (AND), return the logical AND of the children's results.
The initial call evaluateTree(root) will return the final answer.

Walkthrough

The solution is a recursive function that takes a TreeNode as input and returns its boolean evaluation.

Base Case: The recursion stops at the leaf nodes. If a node is a leaf (i.e., node.left and node.right are null), its value is either 0 or 1. We return true if node.val == 1 and false if node.val == 0.

Recursive Step: For any internal node, we first make recursive calls to evaluate its left and right children. boolean leftResult = evaluateTree(node.left); boolean rightResult = evaluateTree(node.right);

Once we have the boolean results from both children, we apply the operation specified by the current node's value. If node.val is 2 (OR), we return leftResult || rightResult. If node.val is 3 (AND), we return leftResult && rightResult.

The initial call to this function with the root of the tree will trigger the evaluation of the entire tree, returning the final boolean result.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public boolean evaluateTree(TreeNode root) {18        // Base Case: The node is a leaf.19        if (root.left == null && root.right == null) {20            return root.val == 1;21        }22 23        // Recursive Step: Evaluate left and right children.24        boolean leftValue = evaluateTree(root.left);25        boolean rightValue = evaluateTree(root.right);26 27        // Combine results based on the current node's operation.28        if (root.val == 2) { // OR29            return leftValue || rightValue;30        } else { // AND (root.val == 3)31            return leftValue && rightValue;32        }33    }34}

Complexity

Time

O(N), where N is the number of nodes. The function visits each node in the tree exactly once.

Space

O(H), where H is the height of the tree. This space is used by the call stack during recursion. In the worst case of a skewed tree, H can be O(N). For a balanced tree, H is O(log N).

Trade-offs

Pros

Very simple, clean, and easy to understand.
The code structure directly mirrors the problem's recursive definition.
More space-efficient than the iterative approach using a map, especially for balanced trees.

Cons

For extremely deep trees (not an issue with the given constraints), it could potentially lead to a stack overflow error.

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean evaluateTree ( TreeNode root ) { return dfs ( root ); } private boolean dfs ( TreeNode root ) { if ( root . left == null && root . right == null ) { return root . val == 1 ; } boolean l = dfs ( root . left ), r = dfs ( root . right ); if ( root . val == 2 ) { return l || r ; } return l && r ; } }

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool evaluateTree ( TreeNode * root ) { return dfs ( root ); } bool dfs ( TreeNode * root ) { if ( ! root -> left && ! root -> right ) return root -> val ; bool l = dfs ( root -> left ), r = dfs ( root -> right ); if ( root -> val == 2 ) return l || r ; return l && r ; } };

1# 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 : def dfs ( root ): if root . left is None and root . right is None : return bool ( root . val ) l , r = dfs ( root . left ), dfs ( root . right ) return ( l or r ) if root . val == 2 else ( l and r ) return dfs ( root )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem