We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Evaluate Boolean Binary Tree

Number: 2416

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Apple

Problem Description

Given a full binary tree where every leaf node holds a boolean value (0 for False, 1 for True) and every non-leaf node holds an operator (2 representing OR and 3 representing AND), determine the boolean result of evaluating the tree. The evaluation is performed by applying the corresponding boolean operations to the results of the left and right subtrees.

Key Insights

  • The binary tree is full, so each non-leaf node has exactly two children.
  • Leaf nodes directly represent boolean values.
  • Non-leaf nodes represent boolean operations: 2 for OR and 3 for AND.
  • A depth-first (post-order) traversal is ideal to evaluate the tree recursively from the bottom up.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes, since each node is visited once.
Space Complexity: O(h) where h is the height of the tree, representing the recursion stack (in the worst-case, O(n) for a skewed tree).

Solution

The solution uses a recursive depth-first search (DFS) approach to evaluate the binary tree. For each node, if it is a leaf, it returns its boolean value. For non-leaf nodes, the function recursively evaluates the left and right children. Depending on the current node's value (2 for OR, 3 for AND), it then applies the respective boolean operator to the evaluated results of its children. The approach leverages the guarantee that the tree is full (each non-leaf node has two children), simplifying the recursion and operation application.

Code Solutions

# Define a TreeNode class to represent nodes of the binary tree.
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 node is a leaf, return its boolean value (True if 1, False if 0)
        if not root.left and not root.right:
            return root.val == 1
        
        # Recursively evaluate the left and right subtrees
        left_value = self.evaluateTree(root.left)
        right_value = self.evaluateTree(root.right)
        
        # If node value is 2, perform OR operation
        if root.val == 2:
            return left_value or right_value
        # If node value is 3, perform AND operation
        elif root.val == 3:
            return left_value and right_value
← Back to All Questions