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.

Examples

Example 1:

graph TD;
    A(OR) --- B(True) & C(AND);

	C --- D(False) & E(True)

Result in:

graph TD;
    A(OR) --- B(True) & C(False);

Results in:

graph TD;
    A(True)
  
1
2
3
4
5
6

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:

1
2
3

Input: root = [0]
Output: false
Explanation: The root node is a leaf node and it evaluates to false, so we return false.

Solution

Method 1 - Recursive DFS

We can perform postorder DFS.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public boolean evaluateTree(TreeNode root) {
	    switch(root.val) {
		    case 0:
			    return false;
			case 1:
				return true;
			case 2: 
				return evaluateTree(root.left) || evaluateTree(root.right);
			default: // case 3
				return evaluateTree(root.left) && evaluateTree(root.right);
				
	    }
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1) (assuming recursive stack is not counted, O(n) otherwise)