algoadvance

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
  • 1 represents True
• Non-leaf nodes have either the value 2 or 3, where:
  • 2 represents the boolean OR operation
  • 3 represents the boolean AND operation

The value of a node in the boolean tree is calculated recursively. Leaf nodes do not have any children, while non-leaf nodes will have exactly two children, left and right.

Write a function to evaluate the boolean value of the root node, considering the children and the operations as described.

Clarifying Questions

1. Input Format: What is the format of the input tree provided?
   • The tree will be given via the TreeNode class definition as described in Leetcode.
2. Output: What should be the output?
   • The output should be a boolean value True or False after evaluating the tree.

Code

# Definition for TreeNode.
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: TreeNode) -> bool:
        if not root:
            return False
        
        # If the node is a leaf node
        if root.left is None and root.right is None:
            return root.val == 1
        
        left_val = self.evaluateTree(root.left)
        right_val = self.evaluateTree(root.right)
        
        if root.val == 2:
            return left_val or right_val
        
        if root.val == 3:
            return left_val and right_val

# Example Usage:
# Let's build a tree to test the function
# Example Tree: [3,2,1,1]
#      3
#     / \
#    2   1
#   / \
#  1   1

root = TreeNode(3, TreeNode(2, TreeNode(1), TreeNode(1)), TreeNode(1))
sol = Solution()
print(sol.evaluateTree(root))  # Expected output: True

Strategy

1. Base case for leaf nodes:
   • If the node is a leaf node (both left and right children are None), return whether the node value is 1 (i.e., True).
2. Recursive evaluation:
   • Recursively evaluate the left and right children.
   • If the current node value is 2, perform the logical OR operation on the results of the left and right children.
   • If the current node value is 3, perform the logical AND operation on the results of the left and right children.
3. Return the result:
   • The final result of the tree evaluation will be returned.

Time Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. This is because we need to visit each node exactly once.
• Space Complexity: O(H), where H is the height of the tree. This space is used by the recursion stack.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?