# Evaluate Boolean Binary Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/evaluate-boolean-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/evaluate-boolean-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
---
## Problem
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:**

![](https://assets.glich.co/dsa/evaluate-boolean-binary-tree/image0.png) 

**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
## Iterative Post-order Traversal with a Map
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Stack;
import java.util.Map;
import java.util.HashMap;

/**
 * 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) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        Map<TreeNode, Boolean> evaluated = new HashMap<>();

        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();

            // Case 1: Node is a leaf
            if (node.left == null && node.right == null) {
                stack.pop();
                evaluated.put(node, node.val == 1);
                continue;
            }

            // Check if children have been evaluated
            boolean leftChildEvaluated = evaluated.containsKey(node.left);
            boolean rightChildEvaluated = evaluated.containsKey(node.right);

            // Case 2: Children have been evaluated, so evaluate the current node
            if (leftChildEvaluated && rightChildEvaluated) {
                stack.pop();
                boolean leftVal = evaluated.get(node.left);
                boolean rightVal = evaluated.get(node.right);
                if (node.val == 2) { // OR
                    evaluated.put(node, leftVal || rightVal);
                } else { // AND (val == 3)
                    evaluated.put(node, leftVal && rightVal);
                }
            } else {
                // Case 3: Children not yet evaluated, push them to the stack
                if (!rightChildEvaluated) {
                    stack.push(node.right);
                }
                if (!leftChildEvaluated) {
                    stack.push(node.left);
                }
            }
        }
        return evaluated.get(root);
    }
}
```
### 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)`.

## Recursive Post-order Traversal
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.
**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).
**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.
### Explanation
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.

```java
/**
 * 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) {
        // Base Case: The node is a leaf.
        if (root.left == null && root.right == null) {
            return root.val == 1;
        }

        // Recursive Step: Evaluate left and right children.
        boolean leftValue = evaluateTree(root.left);
        boolean rightValue = evaluateTree(root.right);

        // Combine results based on the current node's operation.
        if (root.val == 2) { // OR
            return leftValue || rightValue;
        } else { // AND (root.val == 3)
            return leftValue && rightValue;
        }
    }
}
```
### 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.

# Solutions
### Java

```java
/** * 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 ; } }
```

### CPP

```cpp
/** * 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 ; } };
```

### Python

```python
# 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 )
```