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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Evaluate Boolean Binary Tree

Difficulty: Easy

Problem Description

You are given the root of a full binary tree where leaf nodes have either the value 0 (False) or 1 (True), and non-leaf nodes have either the value 2 (OR) or 3 (AND). The goal is to evaluate the boolean result of the root node based on the evaluations of its children.

Key Insights

  • Leaf nodes evaluate to their value (0 or 1).
  • Non-leaf nodes evaluate by applying their boolean operation (OR or AND) to the results of their two children.
  • A full binary tree ensures that every node has either 0 or 2 children.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the tree, as each node is visited once. Space Complexity: O(h) - where h is the height of the tree, due to the recursion stack in depth-first search.

Solution

To solve this problem, we will use a depth-first search (DFS) approach. The algorithm will traverse the binary tree starting from the root. If a node is a leaf (value 0 or 1), we return its value directly. For non-leaf nodes (value 2 for OR and value 3 for AND), we recursively evaluate their two children and apply the corresponding boolean operation.

The data structure used is a binary tree, and the algorithmic approach is recursive depth-first search (DFS).

Code Solutions

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

def evaluateTree(root: TreeNode) -> bool:
    # If the node is a leaf, return its boolean value
    if root.val == 0:
        return False
    elif root.val == 1:
        return True
    
    # Recursively evaluate the left and right children
    left_eval = evaluateTree(root.left)
    right_eval = evaluateTree(root.right)
    
    # Apply the OR operation for value 2 and AND operation for value 3
    if root.val == 2:  # OR operation
        return left_eval or right_eval
    elif root.val == 3:  # AND operation
        return left_eval and right_eval
← Back to All Questions