Checking Equivalence of Expression Trees

Let's explore how to determine if two expression trees are equivalent. We'll start with a straightforward, albeit potentially inefficient, approach and then move towards a more optimized solution.

Naive Approach: Generate All Possible Infix Expressions

A naive approach would be to traverse both trees and generate all possible infix expressions for each. Then, we would compare the sets of generated expressions. If the sets are equal, the trees are equivalent.

This approach is conceptually simple, but highly inefficient due to the combinatorial explosion of possible expressions, especially considering operator precedence and parentheses.

• Big(O) Runtime: Exponential, as the number of possible infix expressions grows rapidly with the size of the tree.
• Big(O) Space Usage: Exponential, to store all generated infix expressions.

Optimal Approach: Canonical Representation Using Frequency Counting

A more efficient approach involves creating a canonical representation of the expressions represented by the trees. Since we're checking for equivalence, rather than identical structure, we can focus on the variables and their frequencies. We can achieve this by traversing each tree and building a frequency table of variables.

Algorithm:

1. Traversal: Perform an in-order traversal of each expression tree.
2. Variable Extraction: For each leaf node (variable), store the variable and its sign.
3. Sign Calculation: The sign of a variable depends on the number of negation operators (-) encountered on the path from the root to the leaf node.
4. Frequency Counting: Maintain a frequency table (e.g., a hash map) for each tree, where keys are variable names, and values are their net counts (positive - negative).
5. Comparison: Compare the two frequency tables. If they are identical, the trees are equivalent.

Example:

Consider two expression trees representing the expressions a - b + a and 2a - b.

• Tree 1: a - b + a will result in a frequency table: {a: 2, b: -1}
• Tree 2: 2a - b will result in a frequency table: {a: 2, b: -1}

Since the frequency tables are equal, the expressions are equivalent.

Edge Cases:

• Empty Trees: If both trees are empty, they are equivalent. If one is empty and the other is not, they are not equivalent.
• Single Variable Trees: If both trees contain a single variable, check if the variables are the same.
• Deeply Nested Negations: Ensure the sign calculation correctly handles multiple nested negations.

Code Example (Python):

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


def build_frequency_map(root, sign=1, freq_map=None):
    if freq_map is None:
        freq_map = {}

    if root is None:
        return freq_map

    if root.val == '+':
        build_frequency_map(root.left, sign, freq_map)
        build_frequency_map(root.right, sign, freq_map)
    elif root.val == '-':
        build_frequency_map(root.left, sign, freq_map)
        build_frequency_map(root.right, -sign, freq_map)
    else:
        freq_map[root.val] = freq_map.get(root.val, 0) + sign

    return freq_map

def are_equivalent(root1, root2):
    freq_map1 = build_frequency_map(root1)
    freq_map2 = build_frequency_map(root2)

    return freq_map1 == freq_map2

# Example Usage:
# Tree 1: a - b + a
root1 = Node('+')
root1.left = Node('-')
root1.right = Node('a')
root1.left.left = Node('a')
root1.left.right = Node('b')

# Tree 2: 2a - b
root2 = Node('-')
root2.left = Node('+')
root2.right = Node('b')
root2.left.left = Node('a')
root2.left.right = Node('a')

print(are_equivalent(root1, root2))  # Output: True

#Tree 3: a + b
root3 = Node('+')
root3.left = Node('a')
root3.right = Node('b')

print(are_equivalent(root1, root3)) # Output: False

• Big(O) Runtime: O(N), where N is the total number of nodes in both trees, as we visit each node once during the traversal.
• Big(O) Space Usage: O(M), where M is the number of unique variables in the trees, due to the space used by the frequency tables.