Problem Description

Given two binary expression trees, root1 and root2, each representing a mathematical expression involving only the '+' operator and single-letter variable operands (like 'a', 'b', etc.), determine whether the two expressions represented by the trees are equivalent.

Two expressions are considered equivalent if, after applying the commutative and associative properties of addition (i.e., a + b == b + a and (a + b) + c == a + (b + c)), they represent the same multiset of variables, regardless of their grouping or order.

Key constraints:

• Each node is either a variable (a lowercase English letter) or the character '+'.
• All operands are single lowercase letters.
• Operator nodes always have exactly two children.

Thought Process

The naive approach would be to compare the trees structurally or to try all possible permutations of operands, but this quickly becomes infeasible as the number of variables grows. Since addition is commutative and associative, the order and grouping of operands do not matter. Thus, the core insight is that two expressions are equivalent if and only if they contain the same variables with the same frequencies, regardless of tree shape or traversal order.

Instead of comparing tree structures, we can focus on counting the occurrences of each variable in both trees. If the counts match for all variables, the expressions are equivalent.

Solution Approach

To determine if two expression trees are equivalent, we will:

1. Traverse each tree (using any traversal: preorder, inorder, or postorder), and for each variable (leaf node), increment its count in a frequency map (hash map or dictionary).
2. Ignore operator nodes (they are always '+') and only process leaf nodes (variables).
3. After traversing both trees, compare the two frequency maps. If they are identical, the trees are equivalent; otherwise, they are not.

This approach is efficient because:

• It visits each node exactly once (O(N) time, where N is the total number of nodes).
• Hash map lookups and updates are O(1) per operation.
• We avoid recursion or permutation logic for commutativity/associativity, since counting is order-agnostic.

Example Walkthrough

Consider the following two expression trees:

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

Traversing Tree 1, we encounter variables: a, b, c. Frequency map: {'a': 1, 'b': 1, 'c': 1}.

Traversing Tree 2, we encounter variables: c, a, b. Frequency map: {'a': 1, 'b': 1, 'c': 1}.

Since both maps are identical, the trees are equivalent.

If Tree 2 instead represented ((c + a) + b + b), the frequency map would be {'a': 1, 'b': 2, 'c': 1}, which does not match Tree 1's map, so they would not be equivalent.

Time and Space Complexity

Brute-force approach: Attempting all permutations or directly comparing all possible tree re-groupings would have factorial time complexity, O(N!), which is infeasible for large trees.

Optimized approach (using frequency maps):

• Time Complexity: O(N), where N is the total number of nodes in both trees. Each node is visited once to count variables.
• Space Complexity: O(V), where V is the number of unique variables. The frequency map stores a count for each unique variable.

Summary

By leveraging the commutative and associative properties of addition, we reduce the problem to counting variable occurrences, ignoring the structure and grouping of the expression trees. This approach is both efficient and robust, providing a clear test for equivalence by simply comparing frequency maps. The solution is elegant because it transforms a potentially complex tree comparison into a straightforward counting problem.

Code Implementation

# Definition for a binary tree node.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:
        def count_vars(node, freq):
            if not node:
                return
            if node.val == '+':
                count_vars(node.left, freq)
                count_vars(node.right, freq)
            else:
                freq[node.val] = freq.get(node.val, 0) + 1
        
        freq1 = {}
        freq2 = {}
        count_vars(root1, freq1)
        count_vars(root2, freq2)
        return freq1 == freq2
      

// Definition for a binary tree node.
struct Node {
    char val;
    Node *left;
    Node *right;
    Node(char x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void countVars(Node* node, unordered_map<char, int>& freq) {
        if (!node) return;
        if (node->val == '+') {
            countVars(node->left, freq);
            countVars(node->right, freq);
        } else {
            freq[node->val]++;
        }
    }
    
    bool checkEquivalence(Node* root1, Node* root2) {
        unordered_map<char, int> freq1, freq2;
        countVars(root1, freq1);
        countVars(root2, freq2);
        return freq1 == freq2;
    }
};
      

// Definition for a binary tree node.
class Node {
    char val;
    Node left;
    Node right;
    Node(char val) { this.val = val; }
}

import java.util.*;

class Solution {
    private void countVars(Node node, Map<Character, Integer> freq) {
        if (node == null) return;
        if (node.val == '+') {
            countVars(node.left, freq);
            countVars(node.right, freq);
        } else {
            freq.put(node.val, freq.getOrDefault(node.val, 0) + 1);
        }
    }
    
    public boolean checkEquivalence(Node root1, Node root2) {
        Map<Character, Integer> freq1 = new HashMap<>();
        Map<Character, Integer> freq2 = new HashMap<>();
        countVars(root1, freq1);
        countVars(root2, freq2);
        return freq1.equals(freq2);
    }
}
      

/**
 * Definition for a binary tree node.
 * function Node(val, left, right) {
 *     this.val = val;
 *     this.left = left;
 *     this.right = right;
 * }
 */

var checkEquivalence = function(root1, root2) {
    function countVars(node, freq) {
        if (!node) return;
        if (node.val === '+') {
            countVars(node.left, freq);
            countVars(node.right, freq);
        } else {
            freq[node.val] = (freq[node.val] || 0) + 1;
        }
    }
    let freq1 = {};
    let freq2 = {};
    countVars(root1, freq1);
    countVars(root2, freq2);
    // Compare frequency maps
    let keys1 = Object.keys(freq1);
    let keys2 = Object.keys(freq2);
    if (keys1.length !== keys2.length) return false;
    for (let key of keys1) {
        if (freq1[key] !== freq2[key]) return false;
    }
    return true;
};