LeetCode: 2331. Evaluate Boolean Binary Tree

The 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

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.

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.

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

bool evaluateTree(TreeNode* root) {
    if (root->val < 2) return (bool)root->val;

    if(root->val == 3)
    return evaluateTree(root->left) && evaluateTree(root->right); 

    return evaluateTree(root->left) || evaluateTree(root->right);
}

Let's break down the code:

1. if (root->val < 2) return (bool)root->val;: This is the base case of the recursion. It checks if the value of the current node root->val is less than 2. If it's less than 2 means it is a leaf, so we returs the boolean representation of root->val. In C++, casting an integer to a boolean will result in true for non-zero values and false for zero. So, it returns true if root->val is 1 and false if it's 0.
2. if (root->val == 3) return evaluateTree(root->left) && evaluateTree(root->right);: This part of the code is executed when the value of the current node is 3 meaning is and and operator. In this case, it recursively evaluates both the left and right subtrees using the evaluateTree function and returns the logical AND (&&) of the results. This means that for a node with a value of 3, both its left and right subtrees must evaluate to true for the function to return true.
3. return evaluateTree(root->left) || evaluateTree(root->right);: If none of the previous conditions are met, this part is executed. It recursively evaluates both the left and right subtrees using the evaluateTree function and returns the logical OR (||) of the results. This means that for a node with any value other than 0, 1, or 3, if at least one of its subtrees evaluates to true, the function returns true.