Evaluate Boolean Binary Tree - Leetcode Solution

Problem Statement:

Given the root node of a boolean expression binary tree, return the boolean result of evaluating it.

Note: A boolean expression binary tree is a binary tree where each node corresponds to a boolean value (true or false), or a boolean operator (AND, OR, or NOT).

Example:

Input: [1,null,0,0,1] Output: false Explanation: Only the leaf nodes 1 and 1 represent true values. The AND operator between the two leaves evaluates to false.

Solution:

To evaluate a boolean expression binary tree, we need to traverse through the tree and evaluate the boolean values and operators at each node.

We can start by recursively traversing down the left subtree and right subtree of the root node. At each node, we can check if the node is a boolean value or a boolean operator.

If the node is a boolean value (true or false), we return the value.

If the node is a boolean operator, we need to evaluate the expression based on the operator type. For AND operator, we return true only if both the left subtree and the right subtree evaluate to true. For OR operator, we return true if either the left subtree or the right subtree evaluates to true. And for NOT operator, we return true if the left subtree evaluates to false.

We can use a switch case statement to determine the operator type and perform the operation accordingly.

Let's look at the code implementation for the same:

Code Implementation:

class Solution:
    def evalBoolExpr(self, root: 'Node') -> bool:
        # if root is a leaf node, return its value
        if root.left is None and root.right is None:
            return root.val == 't'
        
        # evaluate the left subtree
        left = self.evalBoolExpr(root.left)
        
        # evaluate the right subtree
        right = self.evalBoolExpr(root.right)
        
        # check the operator type
        if root.val == 'and':
            return left and right
        elif root.val == 'or':
            return left or right
        else:
            return not left

Time Complexity: The time complexity of this algorithm is O(n), where n is the number of nodes in the boolean expression binary tree. This is because we need to traverse every node in the tree once.

Space Complexity: The space complexity of this algorithm is O(h), where h is the height of the boolean expression binary tree. This is because we need to store the recursive call stack for each node in the longest path from root to leaf.

1