Evaluate Boolean Binary Tree

Easy

Asked by:

14 views

Topics:

TreesRecursion

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What values can the leaf nodes have besides 0 and 1, and what values can the internal nodes have besides 2 and 3?
Can the tree be empty (null root node)? If so, what should I return?
Are we guaranteed a valid binary tree structure, or do I need to handle cases where a node might have only one child?
What does a node with value '2' represent? Is it equivalent to an OR operation, and '3' equivalent to an AND operation?
What is the maximum depth of the tree I should expect?

Brute Force Solution

Approach

Imagine each node in the tree as representing a simple calculation. The brute force way is to look at every single node, one by one, starting from the very bottom and working our way up. We keep applying the calculation each node represents until we reach the very top.

Here's how the algorithm would work step-by-step:

Begin at the bottom of the tree, at the furthest left leaf.
Figure out the result of that leaf's value (it's either true or false).
Move to the next leaf at the bottom and do the same thing.
Once you have the results of the leaves, move up to their parent. Use the parent's operator (either 'AND' or 'OR') and the two children's results to calculate the parent's result.
Repeat this calculation going up the tree, level by level.
At each node, you will have already computed the result of the two nodes beneath it.
Continue performing these calculations until you reach the very top node. The result of that node is the final answer.

Code Implementation

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def evaluate_boolean_binary_tree(root):
    # Base case: If the node is a leaf, return its boolean value.
    if root.left is None and root.right is None:
        return bool(root.value)

    # Recursively evaluate the left and right subtrees.
    left_result = evaluate_boolean_binary_tree(root.left)
    right_result = evaluate_boolean_binary_tree(root.right)

    # Apply the operator based on the node's value.
    # 2 is OR, 3 is AND.
    if root.value == 2:
        # OR operation
        return left_result or right_result

    else:
        # AND operation
        return left_result and right_result

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses the binary tree in a bottom-up manner, evaluating each node once. The number of nodes in the tree is represented by n. Each node evaluation involves a constant amount of work (checking the operator and applying it to the children's results). Since we visit each of the n nodes exactly once, the time complexity is directly proportional to the number of nodes. Therefore, the overall time complexity is O(n).

Space Complexity

O(H) – The space complexity is determined by the recursion depth, where H is the height of the binary tree. In the worst-case scenario, the recursion stack will grow to a depth equal to the height of the tree as we traverse from the leaves to the root. Therefore, the auxiliary space used by the recursive calls is proportional to the height of the tree. Consequently, the space complexity is O(H), which can be O(N) in a skewed tree and O(log N) in a balanced tree, where N is the number of nodes.

Optimal Solution

Approach

The key is to work from the bottom up. Instead of figuring out the entire tree at once, you simplify it piece by piece until you get to the top, where the final answer will be revealed.

Here's how the algorithm would work step-by-step:

Start at the very bottom of the tree, at the leaves. These are the simple 'true' or 'false' values we know.
Move up to the nodes that are right above those leaves. These nodes will have an operator, either 'AND' or 'OR'.
Use the operator to combine the 'true' or 'false' values from the leaves below. For example, if the operator is 'AND' and both leaves are 'true', the node becomes 'true'. If either is 'false', the node becomes 'false'.
Replace the node and its two leaves with the single result you just calculated. This shrinks the tree.
Keep moving up the tree, repeating this process. At each node, use the operator to combine the results from the nodes below.
Eventually, you'll reach the very top of the tree, the root node. The value of this root node will be the final 'true' or 'false' result.

Code Implementation

class TreeNode:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def evaluate_tree(root):
    if not root:
        return False

    if root.left is None and root.right is None:
        return bool(root.value)

    left_value = evaluate_tree(root.left)
    right_value = evaluate_tree(root.right)

    # Evaluate based on the node's boolean operation
    if root.value == 2:
        # Represents the 'OR' operation.
        return left_value or right_value

    else:
        # Represents the 'AND' operation.
        return left_value and right_value

def evaluateTree(root):
    #Evaluate from the bottom up
    return evaluate_tree(root)

Big(O) Analysis

Time Complexity

O(n) – The algorithm processes each node of the binary tree exactly once. We start from the leaves and move upwards, evaluating the boolean expression at each internal node. Since we visit each of the n nodes in the tree a constant number of times to perform the boolean evaluation, the overall time complexity is directly proportional to the number of nodes, n. Therefore, the time complexity is O(n).

Space Complexity

O(H) – The algorithm uses a recursive, depth-first approach. The space complexity is determined by the maximum depth of the recursion, which corresponds to the height (H) of the binary tree. In the worst-case scenario (a skewed tree), the height can be equal to the number of nodes (N), but in a balanced tree, it will be logarithmic, log(N). Therefore, the auxiliary space used for the recursion stack is O(H), where H is the height of the tree, representing the maximum number of function calls on the stack at any given time. Since the plain English focuses on a bottom-up, recursive evaluation, it's solely related to the function call stack.

Edge Cases

Case	How to Handle
Null root node	Return false if the root is null, as there's nothing to evaluate
Single node tree (root only)	Return the root's value directly, assuming a single-node tree's boolean value is itself
Tree with all True values	The algorithm should correctly evaluate to True if all leaf nodes and operations result in True
Tree with all False values	The algorithm should correctly evaluate to False if all leaf nodes and operations result in False
Deeply nested tree leading to stack overflow (if recursive)	Consider iterative solutions to avoid stack overflow errors for very deep trees
Tree where internal nodes have the wrong value (not 2 or 3)	Throw an IllegalArgumentException or return a specific error value to indicate invalid input in cases where an internal node is not 2 or 3.
Mixed True/False values with operations	Ensure 'OR' (2) and 'AND' (3) operations correctly combine True and False values according to boolean logic
Integer overflow during recursive evaluation (if applicable)	The provided problem description doesn't have integer calculation, therefore this is irrelevant

Null root node

How to Handle:

Return false if the root is null, as there's nothing to evaluate

Single node tree (root only)

How to Handle:

Return the root's value directly, assuming a single-node tree's boolean value is itself

Tree with all True values

How to Handle:

The algorithm should correctly evaluate to True if all leaf nodes and operations result in True

Tree with all False values

How to Handle:

The algorithm should correctly evaluate to False if all leaf nodes and operations result in False

Deeply nested tree leading to stack overflow (if recursive)

How to Handle:

Consider iterative solutions to avoid stack overflow errors for very deep trees

Tree where internal nodes have the wrong value (not 2 or 3)

How to Handle:

Throw an IllegalArgumentException or return a specific error value to indicate invalid input in cases where an internal node is not 2 or 3.

Mixed True/False values with operations

How to Handle:

Ensure 'OR' (2) and 'AND' (3) operations correctly combine True and False values according to boolean logic

Integer overflow during recursive evaluation (if applicable)

How to Handle:

The provided problem description doesn't have integer calculation, therefore this is irrelevant