Check If Two Expression Trees are Equivalent solution and explanation
Google
2 more videos on this problem
1612. Check If Two Expression Trees are Equivalent (Leetcode Medium)Programming Live with Larry · 5:21 · 166 views
Leetcode 1612 Check If Two Expression Trees are Equivalent - Explained In HindiAlgorithmicIQ · 13:15 · 5 views
LeetCode 1612: Check If Two Expression Trees are EquivalentAlitaCode · 26:05 · 1 view
The problem
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.valis'+'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
# Definition for a binary tree node.
# class Node(object):
# 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 dfs(root, v):
if root is None:
return
if root.val != '+':
cnt[root.val] += v
dfs(root.left, v)
dfs(root.right, v)
cnt = Counter()
dfs(root1, 1)
dfs(root2, -1)
return all(x == 0 for x in cnt.values())/**
* Definition for a binary tree node.
* class Node {
* char val;
* Node left;
* Node right;
* Node() {this.val = ' ';}
* Node(char val) { this.val = val; }
* Node(char val, Node left, Node right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int[] cnt = new int[26];
public boolean checkEquivalence(Node root1, Node root2) {
dfs(root1, 1);
dfs(root2, -1);
for (int x : cnt) {
if (x != 0) {
return false;
}
}
return true;
}
private void dfs(Node root, int v) {
if (root == null) {
return;
}
if (root.val != '+') {
cnt[root.val - 'a'] += v;
}
dfs(root.left, v);
dfs(root.right, v);
}
}/**
* Definition for a binary tree node.
* struct Node {
* char val;
* Node *left;
* Node *right;
* Node() : val(' '), left(nullptr), right(nullptr) {}
* Node(char x) : val(x), left(nullptr), right(nullptr) {}
* Node(char x, Node *left, Node *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool checkEquivalence(Node* root1, Node* root2) {
int cnt[26]{};
function<void(Node*, int)> dfs = [&](Node* root, int v) {
if (!root) {
return;
}
if (root->val != '+') {
cnt[root->val - 'a'] += v;
}
dfs(root->left, v);
dfs(root->right, v);
};
dfs(root1, 1);
dfs(root2, -1);
for (int& x : cnt) {
if (x) {
return false;
}
}
return true;
}
};/**
* Definition for a binary tree node.
* function Node(val, left, right) {
* this.val = (val===undefined ? " " : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {Node} root1
* @param {Node} root2
* @return {boolean}
*/
var checkEquivalence = function (root1, root2) {
const cnt = new Array(26).fill(0);
const dfs = (root, v) => {
if (!root) {
return;
}
if (root.val !== '+') {
cnt[root.val.charCodeAt(0) - 'a'.charCodeAt(0)] += v;
}
dfs(root.left, v);
dfs(root.right, v);
};
dfs(root1, 1);
dfs(root2, -1);
for (const x of cnt) {
if (x) {
return false;
}
}
return true;
};Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Canonical Serialization with Sorted Subtrees | O(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 |
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.