Check If Two Expression Trees are Equivalent

Check If Two Expression Trees are Equivalent - 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.

Input & Output

Example 1 — Different Structure, Same Expression

$ Input: root1 = ["+","x","y"], root2 = ["+","y","x"]

› Output: true

💡 Note: Both trees represent x + y and y + x. Since addition is commutative, these expressions are equivalent regardless of variable values.

Example 2 — Different Variables

$ Input: root1 = ["+","x","x"], root2 = ["+","y","y"]

› Output: false

💡 Note: First tree represents x + x (or 2x) while second represents y + y (or 2y). These are not equivalent since they depend on different variables.

Example 3 — Complex Nested Expression

$ Input: root1 = ["+",["+","x","y"],"z"], root2 = ["+","z",["+","y","x"]]

› Output: true

💡 Note: Tree 1: (x + y) + z, Tree 2: z + (y + x). Both evaluate to x + y + z due to associativity and commutativity of addition.

Constraints

The number of nodes in both trees are in the range [1, 4000]
Node.val.length <= 5
Node.val consists of digits and lowercase English letters
It's guaranteed that if a node has 2 children, then it is an operator
It's guaranteed that if a node has 0 children, then it is an operand

Visualization

Tap to expand

Understanding the Visualization

Input Trees

Two binary expression trees with different structures

Extract Variables

Count frequency of each variable in both trees

Compare

Trees are equivalent if variable frequencies match

Key Takeaway

🎯 Key Insight: Two addition trees are equivalent if they have identical variable frequency counts, regardless of structure

Asked in

G Google 25 f Facebook 18 a Amazon 12 M Microsoft 8

The key insight is that two addition expression trees are equivalent if they contain the same variables with identical frequencies. Since addition is both commutative (a+b = b+a) and associative ((a+b)+c = a+(b+c)), the structure doesn't matter—only the variable counts. Best approach uses frequency counting with DFS traversal. Time: O(n), Space: O(v + h).

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count Approach	O(n + m)	O(v + h)	Count occurrences of each variable in both trees and compare frequencies
Brute Force Expression Evaluation	O(2^k × n)	O(k + h)	Generate all possible variable assignments and evaluate both trees

Frequency Count Approach — Algorithm Steps

Step 1: Traverse first tree and count variable frequencies
Step 2: Traverse second tree and count variable frequencies
Step 3: Compare the frequency maps
Step 4: Return true if frequencies match exactly

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Tree 1

Traverse first tree counting each variable

Count Tree 2

Traverse second tree counting each variable

Compare Maps

Check if frequency maps are identical

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_VARS 100

struct TreeNode {
    char val[10];
    struct TreeNode* left;
    struct TreeNode* right;
};

struct VarCount {
    char vars[MAX_VARS][10];
    int counts[MAX_VARS];
    int size;
};

struct TreeNode* createNode(const char* val) {
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    strcpy(node->val, val);
    node->left = NULL;
    node->right = NULL;
    return node;
}

void addVar(struct VarCount* vc, const char* var, int count) {
    for (int i = 0; i < vc->size; i++) {
        if (strcmp(vc->vars[i], var) == 0) {
            vc->counts[i] += count;
            return;
        }
    }
    strcpy(vc->vars[vc->size], var);
    vc->counts[vc->size] = count;
    vc->size++;
}

void countVariables(struct TreeNode* node, struct VarCount* vc) {
    if (!node) return;
    
    if (!node->left && !node->right) {
        // Leaf node - it's a variable
        addVar(vc, node->val, 1);
        return;
    }
    
    // Internal node - it's an operator (+)
    countVariables(node->left, vc);
    countVariables(node->right, vc);
}

bool varCountsEqual(struct VarCount* vc1, struct VarCount* vc2) {
    if (vc1->size != vc2->size) return false;
    
    for (int i = 0; i < vc1->size; i++) {
        bool found = false;
        for (int j = 0; j < vc2->size; j++) {
            if (strcmp(vc1->vars[i], vc2->vars[j]) == 0) {
                if (vc1->counts[i] != vc2->counts[j]) return false;
                found = true;
                break;
            }
        }
        if (!found) return false;
    }
    
    return true;
}

bool solution(struct TreeNode* root1, struct TreeNode* root2) {
    struct VarCount vc1 = {.size = 0};
    struct VarCount vc2 = {.size = 0};
    
    countVariables(root1, &vc1);
    countVariables(root2, &vc2);
    
    return varCountsEqual(&vc1, &vc2);
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    // Simple tree building for demonstration
    struct TreeNode* root1 = createNode("x");
    struct TreeNode* root2 = createNode("x");
    
    bool result = solution(root1, root2);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Single traversal of each tree where n and m are node counts

✓ Linear Growth

Space Complexity

O(v + h)

Hash map stores v unique variables, recursion uses O(h) stack space

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

327 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler