Boolean Expression Tree with Leaf Flips

Problem Statement

You are given a binary expression tree representing a boolean expression. The leaves of the tree are boolean values (True or False), and the internal nodes are logical operators (AND, OR).

Implement a structure that supports two operations:

1. evaluate(): Returns the current boolean result of the root.
2. flip(leaf_id): Toggles the boolean value of the leaf with the given ID.

Each node in the tree has a unique id. Internal nodes maintain the result of their children based on their operator. You must optimize the flip operation so that it does not re-evaluate the entire tree.

Function Signature

class Node:
    def __init__(self, id, type, left=None, right=None, val=None):
        self.id = id
        self.type = type # 'AND', 'OR', or 'LEAF'
        self.left = left
        self.right = right
        self.val = val # Only for LEAF nodes

Constraints

• The tree is a full binary tree (every internal node has two children).
• flip must run in O(h) time, where h is the height of the tree.
• evaluate must run in O(1) time.

Example

Consider: Root(AND) -> Left(LEAF: True), Right(OR) -> (LEAF: False, LEAF: True)

1. Initial evaluation: True AND (False OR True) = True.
2. flip(Right-Left): The False becomes True.
3. The tree updates: Right becomes True, Root remains True.

Edge Cases

• Single node trees (leaf only).
• Logical short-circuiting: Note that AND can be False even if one child is False regardless of the other, but for this problem, assume nodes update based on both children values unless optimized.