Check If Two Expression Trees are Equivalent - Solution & Explanation

Problem Overview: You receive two binary expression trees. Leaf nodes contain variables (like a, b, c) and internal nodes contain the '+' operator. Because addition is commutative, the structure of the tree may differ while still representing the same expression. The task is to check whether both trees evaluate to the same expression.

Approach 1: Canonical Serialization of Expression Trees (O(n log n) time, O(n) space)

One way to compare expressions is to convert each tree into a canonical form. Traverse the tree using Depth-First Search and serialize each subtree into a string. For operator nodes, recursively serialize left and right children, then sort the two results before concatenation because a + b equals b + a. This normalization ensures equivalent expressions produce identical serialized strings. Finally, compare the two strings. Sorting child expressions introduces extra overhead, giving roughly O(n log n) time in the worst case and O(n) space for recursion and serialization.

Approach 2: Variable Frequency Counting with DFS (O(n) time, O(k) space)

The key observation: since the only operator is '+', the final expression is simply the sum of all variables in the tree. The tree structure does not matter. Traverse each tree using DFS and count how many times each variable appears. Use a hash table to maintain frequencies. For the first tree, increment counts for each variable. For the second tree, decrement counts. If both trees represent the same expression, all counts end at zero.

This approach works because addition is associative and commutative, meaning order and grouping do not affect the result. The traversal touches each node exactly once, giving O(n) time. Space complexity is O(k), where k is the number of unique variables. Implementation is straightforward using recursion over the binary tree.

Recommended for interviews: The DFS frequency counting approach. It demonstrates the key insight that tree structure is irrelevant when the operator is commutative. Interviewers expect candidates to recognize this simplification and reduce the problem to counting variables with a hash map. Mentioning the serialization approach first shows you considered structural comparison, but identifying the O(n) counting solution demonstrates stronger problem-solving skills.