Check If Two Expression Trees are Equivalent

Check If Two Expression Trees are Equivalent

What is this problem about?

An expression tree is a binary tree where each node is either an operand (a variable or a number) or an operator (+, -, *, /). In this problem, we are specifically dealing with commutative operations like addition (+). Two trees are equivalent if they evaluate to the same value for all possible values of their variables. You are given the roots of two such trees and need to determine if they are equivalent.

Why is this asked in interviews?

Google asks this to test your understanding of Tree Traversal (DFS) and your ability to handle commutative properties. It’s not enough to check if the trees are identical in structure; $a + b$ is the same as $b + a$. It evaluates whether you can use a Hash Table or a Frequency Map to "normalize" the expression and compare the counts of operands across different subtrees.

Algorithmic pattern used

This problem uses the Depth-First Search (DFS) or Post-order Traversal pattern combined with a Hash Table. Since addition is commutative, the order of children doesn't matter. You can recursively calculate a frequency map for each subtree, where the keys are the operands and the values are their counts. Two trees are equivalent if their final root frequency maps are identical.

Example explanation

Tree 1: (a + b) + c

• Left child (a+b) produces map: {a:1, b:1}
• Root (+) combines with 'c' map: {a:1, b:1, c:1} Tree 2: a + (c + b)
• Right child (c+b) produces map: {c:1, b:1}
• Root (+) combines with 'a' map: {a:1, b:1, c:1} The final maps match, so the trees are equivalent.

Common mistakes candidates make

The most common mistake is only checking if the trees are identical in structure (i.e., tree1.left == tree2.left). Another is not correctly merging frequency maps from children during the post-order traversal. Some might try to evaluate the expression by assigning random numbers to variables, which can lead to collisions and incorrect results (though it's a clever heuristic).

Interview preparation tip

When dealing with "equivalence" in structures that have commutative properties (like math expressions or sets), think about how to "flatten" or "canonicalize" the data. Frequency maps are a standard way to ignore order while preserving content.