LeetCode 1612 - Check If Two Expression Trees are Equivalent

The problem asks us to determine whether two binary expression trees are equivalent, where equivalence is defined as the trees representing the same arithmetic expression, modulo the order of addition since addition is commutative.

leetcodemediumhash-tabletreedepth-first-searchbinary-treecounting

LeetCode Problem 1612

Difficulty: 🟡 Medium
Topics: Hash Table, Tree, Depth-First Search, Binary Tree, Counting

Solution

Problem Understanding

The problem asks us to determine whether two binary expression trees are equivalent, where equivalence is defined as the trees representing the same arithmetic expression, modulo the order of addition since addition is commutative. Each tree node contains either a '+' operator (for internal nodes) or a variable (for leaf nodes). The input consists of two root nodes of such binary expression trees. The expected output is a boolean, true if the trees are equivalent and false otherwise.

The constraints specify that each tree has an odd number of nodes, at most 4999 nodes, and every node is guaranteed to be a valid binary expression tree. The small upper bound on nodes allows for recursive or DFS-based solutions. Important edge cases include trees with a single node (a single variable), trees where all additions are nested differently, and trees containing repeated variables.

Approaches

The naive or brute-force approach is to try evaluating all possible permutations of addition operations, which is infeasible since the number of permutations grows factorially with the number of operands. This approach is correct in principle but extremely inefficient for larger trees.

The key observation for a better solution is that addition is commutative and associative. This allows us to represent each expression tree as a multiset (or counter) of its leaf variables. By recursively flattening the tree and counting occurrences of each variable, we can compare the two trees efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n!) Generate all permutations of addition order; infeasible for n > 10
Optimal O(n) O(n) Flatten tree to multiset of variables using DFS and compare

Algorithm Walkthrough

  1. Define a recursive helper function flatten(node) that returns a Counter of variables in the subtree rooted at node.
  2. If node is None, return an empty Counter.
  3. If node.val is a variable (not '+'), return a Counter containing that variable with count 1.
  4. If node.val is '+', recursively call flatten on node.left and node.right, then merge the two Counter objects by addition.
  5. Use the helper to flatten both root1 and root2 into two Counter objects.
  6. Compare the two Counter objects for equality. Return true if equal, false otherwise.

Why it works: The flattening function effectively computes the multiset of variables for each subtree. Because addition is commutative and associative, the sum of variables is invariant under different tree shapes. Comparing these multisets ensures equivalence without considering tree structure.

Python Solution

from collections import Counter

# 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 flatten(node: 'Node') -> Counter:
            if not node:
                return Counter()
            if node.val != '+':
                return Counter([node.val])
            left_count = flatten(node.left)
            right_count = flatten(node.right)
            return left_count + right_count
        
        return flatten(root1) == flatten(root2)

Implementation explanation: The flatten helper function traverses the tree in DFS order. Leaf nodes produce a single-element counter. Internal nodes with '+' merge the counts from their children. The equality comparison of counters correctly captures commutative equivalence of addition.

Go Solution

package main

import "reflect"

// Definition for a binary tree node.
type Node struct {
    Val   string
    Left  *Node
    Right *Node
}

type Solution struct{}

func (s *Solution) CheckEquivalence(root1 *Node, root2 *Node) bool {
    var flatten func(node *Node) map[string]int
    flatten = func(node *Node) map[string]int {
        if node == nil {
            return map[string]int{}
        }
        if node.Val != "+" {
            return map[string]int{node.Val: 1}
        }
        leftMap := flatten(node.Left)
        rightMap := flatten(node.Right)
        for k, v := range rightMap {
            leftMap[k] += v
        }
        return leftMap
    }

    leftCount := flatten(root1)
    rightCount := flatten(root2)
    return reflect.DeepEqual(leftCount, rightCount)
}

Go-specific notes: We use map[string]int instead of Counter. Merging maps requires iterating through keys and incrementing counts. The equality check uses reflect.DeepEqual because Go maps do not support direct equality comparison.

Worked Examples

Example 1:

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

Flattened counts: Counter({'x': 1}) vs Counter({'x': 1})

Output: true

Example 2:

Input:

root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,c]

Flattening root1: Counter({'a':1, 'b':1, 'c':1})

Flattening root2: Counter({'a':1, 'b':1, 'c':1})

Output: true

Example 3:

Input:

root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,d]

Flattening root1: Counter({'a':1, 'b':1, 'c':1})

Flattening root2: Counter({'a':1, 'b':1, 'd':1})

Output: false

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited exactly once in the DFS traversal.
Space O(n) The recursion stack can go up to the height of the tree, and the Counter/map stores all leaf variables.

Test Cases

# Provided examples
assert Solution().checkEquivalence(Node("x")) == True  # single-node trees
root1 = Node("+", Node("a"), Node("+", Node("b"), Node("c")))
root2 = Node("+", Node("+", Node("a"), Node("b")), Node("c"))
assert Solution().checkEquivalence(root1, root2) == True  # a + (b + c) == (a + b) + c
root3 = Node("+", Node("a"), Node("+", Node("b"), Node("c")))
root4 = Node("+", Node("+", Node("a"), Node("b")), Node("d"))
assert Solution().checkEquivalence(root3, root4) == False  # a + (b + c) != (a + b) + d

# Additional cases
assert Solution().checkEquivalence(Node("a"), Node("b")) == False  # different single leaves
root5 = Node("+", Node("a"), Node("a"))
root6 = Node("+", Node("a"), Node("a"))
assert Solution().checkEquivalence(root5, root6) == True  # repeated variable
root7 = Node("+", Node("a"), Node("b"))
root8 = Node("+", Node("b"), Node("a"))
assert Solution().checkEquivalence(root7, root8) == True  # commutative addition
Test Why
x vs x single-node equality
a+(b+c) vs (a+b)+c associativity and commutativity
a+(b+c) vs (a+b)+d different variables produce false
a vs b single-node mismatch
a+a vs a+a repeated variables
a+b vs b+a order of addition

Edge Cases

One important edge case is when both trees consist of a single leaf node. Naive implementations that assume two children for every node might fail. Our flatten function handles this naturally by returning a counter for a leaf node.

A second edge case is when a variable appears multiple times. The counter correctly accumulates occurrences, which ensures repeated variables are compared accurately.

A third edge case is an unbalanced tree, such as a+(b+(c+(d+e))) vs ((a+b)+c)+(d+e). Flattening converts these to a single multiset of variables, ensuring equivalence is detected regardless of tree shape.

This approach scales correctly for all valid inputs, preserves commutative and associative properties of addition, and handles duplicate variables seamlessly.