Problem Description

You are given two binary expression trees where each tree represents an arithmetic expression using only the addition (+) operator. In these trees:

• Internal nodes (nodes with two children) contain the + operator
• Leaf nodes (nodes with no children) contain variable names (operands)

Your task is to determine if the two trees are equivalent, meaning they would evaluate to the same value regardless of what values are assigned to the variables.

For example, if one tree represents a + b and another represents b + a, they are equivalent because addition is commutative. Similarly, (a + b) + c and a + (b + c) are equivalent due to the associative property of addition.

The key insight is that two expression trees with only addition are equivalent if and only if they contain the same variables with the same frequencies (since addition is both commutative and associative).

The solution counts the frequency of each variable in both trees. It increments the count for variables in the first tree and decrements for variables in the second tree. If all counts end up as zero, the trees have identical variable compositions and are therefore equivalent.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a binary tree structure, which is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with binary expression trees. Trees are connected acyclic graphs with a hierarchical structure.

DFS

• Yes: Since we're dealing with a tree structure, DFS (Depth-First Search) is the natural choice for traversal.

Conclusion: The flowchart suggests using DFS for this problem.

This makes perfect sense because:

1. We need to traverse both binary expression trees completely to count all the variables (leaf nodes)
2. DFS allows us to recursively visit each node and its children
3. When we encounter a leaf node (where root.val != '+'), we can record the variable
4. The recursive nature of DFS perfectly matches the recursive structure of trees

The solution implements DFS through the dfs function that:

• Recursively traverses each tree
• Counts occurrences of variables in the first tree (with +1)
• Decrements counts for variables in the second tree (with -1)
• If the trees are equivalent, all variable counts will cancel out to zero

Intuition

Since we're dealing with expression trees that only contain the addition operator, we can leverage an important mathematical property: addition is both commutative (a + b = b + a) and associative ((a + b) + c = a + (b + c)). This means that no matter how we rearrange or regroup the additions, as long as we're adding the same variables the same number of times, we'll get the same result.

Think of it like having two bags of colored marbles. If both bags contain the exact same marbles (same colors, same quantities), then no matter how you arrange or group them when pouring them out, you'll end up with the same collection. Similarly, two expression trees with only addition are equivalent if they contain the same variables with the same frequencies.

The key insight is that we don't need to evaluate the expressions or compare the tree structures directly. Instead, we can simply count how many times each variable appears in each tree. If the counts match, the trees must be equivalent.

The clever trick in the solution is to use a single counter with positive and negative values. When traversing the first tree, we add +1 for each variable occurrence. When traversing the second tree, we add -1 for each variable occurrence. If the trees are equivalent (same variables, same frequencies), all the positive counts from tree 1 will be perfectly canceled out by the negative counts from tree 2, leaving us with all zeros.

This approach transforms a potentially complex structural comparison problem into a simple counting problem, making it both elegant and efficient.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The solution uses a DFS traversal combined with a frequency counter to determine if two expression trees are equivalent.

Implementation Details:

1. Counter Data Structure: We use a Counter (hash map) to track the frequency of each variable across both trees. The key insight is using a single counter with signed values:

   • Variables from root1 contribute +1 to the count
   • Variables from root2 contribute -1 to the count

2. DFS Traversal Function: The dfs function takes two parameters:

   • root: The current node being visited
   • v: The value to add to the counter (+1 for tree1, -1 for tree2)

3. Traversal Logic:

   def dfs(root, v):
       if root is None:
           return
       if root.val != '+':
           cnt[root.val] += v
       dfs(root.left, v)
       dfs(root.right, v)

   • Base case: If the node is None, return immediately
   • If the node's value is not '+', it's a leaf node (variable), so we update its count
   • Recursively traverse left and right subtrees

4. Main Algorithm:

   • Initialize an empty counter
   • Traverse the first tree with dfs(root1, 1) to add all variables
   • Traverse the second tree with dfs(root2, -1) to subtract all variables
   • Check if all values in the counter are zero using all(x == 0 for x in cnt.values())

Why This Works: If both trees contain the same variables with the same frequencies, each variable's count will be incremented exactly as many times as it's decremented, resulting in a final count of zero. Any non-zero value indicates a mismatch in variable frequencies, meaning the trees are not equivalent.

Time Complexity: O(n + m) where n and m are the number of nodes in the two trees, as we visit each node exactly once.

Space Complexity: O(h + v) where h is the maximum height of the trees (for recursion stack) and v is the number of unique variables.

Example Walkthrough

Let's walk through a concrete example to see how the solution works.

Example Trees:

• Tree 1 represents: (a + b) + c
• Tree 2 represents: a + (c + b)

Tree 1:           Tree 2:
    +                 +
   / \               / \
  +   c             a   +
 / \                   / \
a   b                 c   b

Step-by-step execution:

1. Initialize counter: cnt = {}

2. Traverse Tree 1 with dfs(root1, 1):

   • Visit root +: Skip (it's an operator)
   • Go left to +: Skip (it's an operator)
     • Go left to a: cnt['a'] += 1 → cnt = {'a': 1}
     • Go right to b: cnt['b'] += 1 → cnt = {'a': 1, 'b': 1}
   • Go right to c: cnt['c'] += 1 → cnt = {'a': 1, 'b': 1, 'c': 1}

3. Traverse Tree 2 with dfs(root2, -1):

   • Visit root +: Skip (it's an operator)
   • Go left to a: cnt['a'] += -1 → cnt = {'a': 0, 'b': 1, 'c': 1}
   • Go right to +: Skip (it's an operator)
     • Go left to c: cnt['c'] += -1 → cnt = {'a': 0, 'b': 1, 'c': 0}
     • Go right to b: cnt['b'] += -1 → cnt = {'a': 0, 'b': 0, 'c': 0}

4. Check if all values are zero:

   • cnt = {'a': 0, 'b': 0, 'c': 0}
   • All values are 0, so return True - the trees are equivalent!

Counter-example (non-equivalent trees): If Tree 2 had been a + (b + b) instead:

• After traversing Tree 1: cnt = {'a': 1, 'b': 1, 'c': 1}
• After traversing Tree 2: cnt = {'a': 0, 'b': -1, 'c': 1}
• Since we have non-zero values, return False - the trees are not equivalent

The beauty of this approach is that it automatically handles the commutative and associative properties of addition by simply counting occurrences, without needing to worry about tree structure or parenthesization.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m) where n is the number of nodes in root1 and m is the number of nodes in root2.

The algorithm performs a depth-first search (DFS) traversal on both trees:

• DFS on root1 visits all n nodes exactly once
• DFS on root2 visits all m nodes exactly once
• The final check all(x == 0 for x in cnt.values()) iterates through at most 26 values (assuming lowercase letters), which is O(1)

Therefore, the total time complexity is O(n + m).

Space Complexity: O(h1 + h2 + k) where h1 is the height of root1, h2 is the height of root2, and k is the number of unique leaf values (variables).

The space is used for:

• Recursive call stack for DFS on root1: O(h1) in the worst case
• Recursive call stack for DFS on root2: O(h2) in the worst case
• Counter dictionary cnt: O(k) where k is the number of unique leaf values (at most 26 for lowercase letters)

In the worst case of a skewed tree, the height could be O(n) and O(m) respectively, making the space complexity O(n + m) in the worst case. In the best case of a balanced tree, the heights would be O(log n) and O(log m), making the space complexity O(log n + log m + k).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Identifying Leaf Nodes

A common mistake is assuming that leaf nodes are identified by checking node.left is None and node.right is None. However, the problem guarantees that internal nodes always have exactly two children (binary expression tree property), so checking node.val != '+' is sufficient and more direct.

Incorrect approach:

def dfs(root, v):
    if root is None:
        return
    # Wrong: overly complex check
    if root.left is None and root.right is None:
        cnt[root.val] += v
    dfs(root.left, v)
    dfs(root.right, v)

Correct approach:

def dfs(root, v):
    if root is None:
        return
    # Correct: simpler and clearer
    if root.val != '+':
        cnt[root.val] += v
    dfs(root.left, v)
    dfs(root.right, v)

2. Using Two Separate Counters

Some developers might use two separate counters for each tree and then compare them, which adds unnecessary complexity and potential for errors when comparing dictionaries with different keys.

Inefficient approach:

def checkEquivalence(self, root1, root2):
    cnt1 = Counter()
    cnt2 = Counter()

    def dfs(root, counter):
        if root is None:
            return
        if root.val != '+':
            counter[root.val] += 1
        dfs(root.left, counter)
        dfs(root.right, counter)

    dfs(root1, cnt1)
    dfs(root2, cnt2)

    # Pitfall: comparing counters directly might miss keys present in only one
    return cnt1 == cnt2  # This works but is less elegant

3. Forgetting to Handle None Nodes

If either root1 or root2 could be None (empty tree), the solution should handle this edge case properly. The current solution handles it correctly through the base case in the DFS function.

Missing edge case handling:

def checkEquivalence(self, root1, root2):
    # Pitfall: not explicitly handling None inputs
    cnt = Counter()
    dfs(root1, 1)   # Could fail if root1 is None and dfs doesn't handle it
    dfs(root2, -1)  # Could fail if root2 is None and dfs doesn't handle it

4. Using the Wrong Sign Convention

Mixing up the increment/decrement values (+1 and -1) would lead to incorrect results. Always ensure the first tree adds to the counter and the second tree subtracts.

Wrong sign convention:

# Incorrect: using the same sign for both trees
dfs(root1, 1)
dfs(root2, 1)  # Should be -1

# Or incorrect: reversed signs
dfs(root1, -1)  # Should be 1
dfs(root2, 1)   # Should be -1

5. Inefficient Final Check

Using len(cnt) == 0 or checking if the counter is empty would be incorrect since the counter will contain entries even when all values are zero.

Incorrect final check:

# Wrong: Counter with all zero values is not empty
return len(cnt) == 0

# Wrong: Counter with zero values still has keys
return not cnt

# Correct approach:
return all(x == 0 for x in cnt.values())