We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check If Two Expression Trees are Equivalent

Number: 1750

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given two binary expression trees that represent arithmetic expressions using only the '+' operator and lowercase English letters as operands, determine if the two trees are equivalent. Two expression trees are equivalent if they evaluate to the same result for any assignment of values to the variables. In other words, since addition is both commutative and associative, the trees are equivalent if, after fully expanding each expression, the frequency count of each variable is the same in both trees.

Key Insights

  • Each leaf node in the tree is an operand (a variable) and each internal node represents the '+' operator.
  • Since addition is commutative and associative, the order or grouping of the operands does not affect the result.
  • A simple yet effective strategy is to perform a DFS traversal on each tree and accumulate a frequency count for each variable.
  • Finally, compare the resulting frequency maps from both trees. If they are identical, the trees are equivalent.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes in the tree, as we visit each node once. Space Complexity: O(n) for the recursive stack (in worst-case skewed trees) and the storage used for frequency maps.

Solution

We solve the problem by leveraging a depth-first search (DFS) to traverse each expression tree. For each node:

  • If it is a leaf (i.e., a variable), return a frequency map with that variable counted once.
  • If it is an internal node with the '+' operator, recursively compute the frequency maps from the left and right children, then merge these maps by summing the counts for each variable.

After processing both trees into their respective frequency maps, we simply compare the two maps. If they match exactly, the trees are equivalent; otherwise, they are not.

An important mental note is that the problem simplifies due to the properties of addition, making it unnecessary to worry about parentheses or operator precedence.

Code Solutions

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def checkEquivalence(self, root1: TreeNode, root2: TreeNode) -> bool:
        # Helper function to compute frequency counts of variables in the expression tree.
        def dfs(node):
            # If node is None, return an empty dictionary.
            if not node:
                return {}
            # If the node is a leaf (variable), return a dictionary with a count of 1.
            if not node.left and not node.right:
                return {node.val: 1}
            # Otherwise, the node is an operator (+). Recursively compute counts for left and right children.
            left_counts = dfs(node.left)
            right_counts = dfs(node.right)
            # Merge the two dictionaries.
            for var, count in right_counts.items():
                left_counts[var] = left_counts.get(var, 0) + count
            return left_counts
        
        # Compute frequency maps for both trees.
        counts1 = dfs(root1)
        counts2 = dfs(root2)
        
        # Compare the two frequency maps.
        return counts1 == counts2

# Example usage:
# sol = Solution()
# result = sol.checkEquivalence(root1, root2)
← Back to All Questions