Depth First Search Algorithm to Check If Two Expression Trees are Equivalent

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

expression-binary-tree

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.

Follow up: What will you change in your solution if the tree also supports the ‘-‘ operator (i.e. subtraction)?

Example 1:
Input: root1 = [x], root2 = [x]
Output: true

Example 2:
Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
Output: true
Explaination: a + (b + c) == (b + c) + a

Example 3:
Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
Output: false
Explaination: 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.

Hints:
Count for each variable how many times it appeared in the first tree.
Do the same for the second tree and check if the count is the same for both tree.

Depth First Search Algorithm with Hash Table

Since the expression tree is binary and can only contain one plus symbol. Therefore, we can perform the Depth First Search Algorithm (DFS) on both binary expression trees and count each variables. The two expression trees are equal if both trees contain same number of variables.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 * 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) {
        if (root1 == root2) return true;
        unordered_map<char, int> count1, count2;
        dfs(root1, count1);
        dfs(root2, count2);
        return count1 == count2;
    }
    
private:        
    void dfs(Node* root, unordered_map<char, int> &count) {
        if (!root) return ;
        if (root->val != '+') count[root->val] ++;
        dfs(root->left, count);
        dfs(root->right, count);
    }
};

/**
 * 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) {
        if (root1 == root2) return true;
        unordered_map<char, int> count1, count2;
        dfs(root1, count1);
        dfs(root2, count2);
        return count1 == count2;
    }
    
private:        
    void dfs(Node* root, unordered_map<char, int> &count) {
        if (!root) return ;
        if (root->val != '+') count[root->val] ++;
        dfs(root->left, count);
        dfs(root->right, count);
    }
};

The DFS runs in O(N) time where N is the number of the nodes in both binary expression trees. The space complexity is O(N) as we are using stack via recursion and also need to recording the counters for each variable.

To compare if two hash map are equal (unordered_map), we can simply compare them in C++ using the double equal sign.

–EOF (The Ultimate Computing & Technology Blog) —