Is Check If Two Expression Trees are Equivalent easy or hard?

The problem is classified as Medium on LeetCode. The challenge is recognizing that the '+' operator makes the expression order irrelevant. Once you reduce the problem to counting variables with DFS and a hash map, the implementation becomes straightforward.

Check If Two Expression Trees are Equivalent Python/Java solution

Most implementations perform a DFS traversal and store variable counts in a dictionary (Python) or HashMap (Java). The first traversal increments counts and the second traversal decrements them. After both traversals, checking that all values are zero confirms equivalence. This implementation runs in O(n) time.

How to solve Check If Two Expression Trees are Equivalent in O(n)?

Traverse both trees using depth‑first search. Maintain a hash map counting how many times each variable appears. Increment counts while traversing the first tree and decrement while traversing the second tree. If the final map contains only zeros, the expressions are equivalent. This works because addition is commutative and associative.

What is the best approach for Check If Two Expression Trees are Equivalent?

The most efficient approach uses DFS with a hash map to count variable frequencies. Traverse the first tree and increment counts for each variable, then traverse the second tree and decrement counts. If all counts become zero, both trees represent the same expression. This runs in O(n) time with O(k) space where k is the number of unique variables.

Is Check If Two Expression Trees are Equivalent asked at Google/Amazon/Meta?

Expression tree problems frequently appear in interviews at companies like Google, Amazon, and Meta because they combine tree traversal with algebraic reasoning. Variants involving expression simplification or tree equivalence are common in systems and infrastructure interview rounds.

What data structure is used in Check If Two Expression Trees are Equivalent?

The core data structures are a binary tree for representing the expression and a hash table for counting variable frequencies. Depth‑first search is used to traverse the tree while updating the frequency map.

What is the time complexity of Check If Two Expression Trees are Equivalent?

The optimal solution runs in O(n) time because each node in both trees is visited exactly once during DFS traversal. Space complexity is O(k) for the hash table storing variable frequencies and O(h) recursion stack where h is the tree height.

Description Hints 2 Solution Video 5:21

1612. Check If Two Expression Trees are Equivalent

Medium71.8% acceptance1 companyPremium elsewhere, free here

A binary expression tree is a kind of binary tree used to represent arithmetic expressions. Each node of a binary expression tree has either zero or two children. Leaf nodes (nodes with 0 children) correspond to operands (variables), and internal nodes (nodes with two children) correspond to the operators. In this problem, we only consider the '+' operator (i.e. addition).

You are given the roots of two binary expression trees, root1 and root2. Return true if the two binary expression trees are equivalent. Otherwise, return false.

Two binary expression trees are equivalent if they evaluate to the same value regardless of what the variables are set to.

Example 1:

Input: root1 = [x], root2 = [x]
Output: true

Example 2:

Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,c]
Output: true
Explanation: a + (b + c) == (b + c) + a

Example 3:

Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,d]
Output: false
Explanation: a + (b + c) != (b + d) + a

Constraints:

The number of nodes in both trees are equal, odd and, in the range [1, 4999].
Node.val is '+' or a lower-case English letter.
It's guaranteed that the tree given is a valid binary expression tree.

Follow up: What will you change in your solution if the tree also supports the '-' operator (i.e. subtraction)?

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

Count for each variable how many times it appeared in the first tree.

Hint 2

Do the same for the second tree and check if the count is the same for both tree.

5:21

Still stuck?Read the written solution, or watch a walkthrough.

Open solution