Skip to main content
Talentd

Check If Two Expression Trees are Equivalent - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableTreeDepth-First SearchBinary Tree6 min readAsked at: Google
Practice this problem

Problem Statement

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)?

Approach Overview

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.

Solution

Code

PythonJavaC++JavaScript

Python

Java

C++

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Canonical Serialization with Sorted SubtreesO(n log n)O(n)Useful when comparing full expression structure or when multiple operators exist
DFS Variable Frequency Counting (Hash Map)O(n)O(k)Best approach when operator is '+' and order does not matter

Video Solution

1612. Check If Two Expression Trees are Equivalent (Leetcode Medium) • Programming Live with Larry • 166 views views

Watch 2 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Check If Two Expression Trees are Equivalent with our built-in code editor and test cases.

Practice on FleetCode
Previous

Build Binary Expression Tree From Infix Expression

Next

Evaluate Boolean Binary Tree