1612. Check If Two Expression Trees are Equivalent

Problem Description

The problem presents us with the concept of binary expression trees, which are a type of binary tree specifically used to represent arithmetic expressions involving operators and operands (variables). In the context of this problem, we are focused solely on the '+' operator, denoting addition.

We are given two such binary expression trees, root1 and root2, and our task is to determine whether these two trees are equivalent in terms of their evaluation. Two binary expression trees are considered equivalent if they evaluate to the same value, regardless of how the variables (operands) are valued.

The problem is ultimately asking us to verify if these two trees, when the expressions they represent are evaluated, yield the same result.

Flowchart Walkthrough

To determine the appropriate algorithm using the provided Flowchart for solving LeetCode problem 1612, "Check If Two Expression Trees are Equivalent," let's walk through the series of decisions represented by the nodes and edges in the flowchart:

1. Is it a graph?

Yes: Although the problem doesn't explicitly mention "graph," the expression trees can be considered as special cases of graphs where each node (representing an operator or operand) potentially connects to its child nodes.

2. Is it a tree?

Yes: The problem specifically involves expression trees, which are a type of graph.

3. Is the problem related to directed acyclic graphs (DAGs)?

Yes: All trees are DAGs by definition, as they are directed from the parent to child nodes and do not contain cycles.

4. Is the problem related to topological sort?

No: The goal is not to sort or linearize the nodes but to compare two trees for equivalence, which involves traversing and comparing nodes and subtrees.

Because the flowchart paths specify Depth-First Search (DFS) for tree traversal and comparison, we determine that DFS is the appropriate method for this problem. The trees must be traversed deeply to compare the subtrees and values accurately, making DFS an ideal choice. More detailed steps will involve recursive comparison of nodes to confirm if two trees are structurally identical and have the same values at corresponding positions.

Conclusion: The flowchart suggests using DFS for this tree comparison problem where nodes are checked deeply for equivalence.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To determine if two binary expression trees are equivalent, we have to confirm that they evaluate to the same sum. However, comparing trees directly on their structure can be complex due to the potential different arrangement of nodes (consider the associative property of addition).

Therefore, instead of comparing the structure of the trees, we can compare the summarized results of what they represent. We can traverse each tree and count the occurrences of each variable (operand) by performing a depth-first search (DFS). Since we are only dealing with addition in this scenario, we can represent each variable as a unique index in a list and increment the count at that index.

During the DFS, when we encounter a leaf node (which represents a variable), we identify the corresponding index by subtracting the ASCII value of 'a' from the ASCII value of the variable. This converts the character variable to an integer index (e.g., 'a' becomes 0, 'b' becomes 1, ..., 'z' becomes 25). We then increment the count at this index by 1. For internal nodes, which correspond to the '+' operator, we simply sum the counters from both children nodes.

After we have completed the DFS for both trees, we obtain two lists of counts representing the frequency of all variables from both trees. If these two lists are identical, it means that the trees are equivalent because the collections of variables and their counts match, and thus, they will evaluate to the same total sum regardless of the specific values assigned to the variables.

The given Python function checkEquivalence includes the implementation of this approach. The nested dfs function is responsible for the DFS traversal and count computation. Finally, we compare the count lists from both root1 and root2 and return True if they are equal, indicating equivalence, or False otherwise.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The solution employs a depth-first search (DFS) algorithm, which is adept at traversing and processing all nodes of a binary tree. DFS is particularly useful in this context as it allows us to navigate through each branch of the tree and aggregate data (in this case, counts of variables) along the way from leaf nodes up to the root.

Here's a step-by-step breakup of the DFS implementation found in the provided solution code:

A recursive dfs function is defined that will traverse the tree starting from a given node (root).
An array cnt of size 26 is initialized to keep track of the count of each variable ('a' to 'z'), where the index corresponds to the variable (0 for 'a', 1 for 'b', ..., 25 for 'z').
The base case of the recursion is when the current node is None. In such a case, cnt is returned as it is because there are no variables to count.
The recursive case checks if the current node contains a value that is an operand (i.e., not '+' or '-'). If it's an operand, it increments the count corresponding to the variable in cnt.
If the current node is an operator node ('+'), the dfs function is called on both the left and right subtrees. The counts from both subtrees are then combined by summing their corresponding elements.
It's important to note that only the '+' operator is being considered, and as such, the sum of the left and right subtree counts is always appropriate (there's no code handling subtraction, because '-' operators are not part of the problem's scope).
After computing the counts for both trees using the dfs function, the results are compared using return dfs(root1) == dfs(root2).
If the counts match, this means that the trees are equivalent (regardless of the actual values of operands, they will evaluate to the same total), and the function returns True; otherwise, it returns False.

The dfs function operates by post-order traversal—first, the left subtree is processed, then the right subtree, and finally the current node. This approach guarantees that counts are aggregated from the bottom up, ensuring that each internal node correctly sums the counts of its child nodes.

In terms of data structures, the solution uses a basic Python list (cnt) to hold the counts of variables. The use of such a simple data structure is possible because of the limited set of characters (only lowercase alphabetic characters) and the simplicity of the operation (only addition).

By leveraging the recurrence and simplicity of DFS, this solution elegantly reduces the problem to a comparison of variable frequencies, thus avoiding the need to directly compare the binary tree structures or evaluate any expressions that the trees might represent.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple example with two binary expression trees representing the expressions (a + (b + c)) and ((b + a) + c). These trees are structured differently but evaluate to the same value regardless of the actual numerical values assigned to a, b, and c.

Here's what the two binary expression trees might look like:

    Tree 1               Tree 2
      +                    +
     / \                  / \
    a   +                +   c
       / \              / \
      b   c            b   a

As per the solution approach, we will walk through the DFS algorithm to count occurrences of each variable.

For Tree 1:

Start at the root and call dfs with the root node (which contains '+').
Since the root node is '+', recur for the left and right child.
- For the left child (which is 'a'), there's no child, so increment the count for 'a' by 1.
- For the right child (which contains '+'), recur for its children.
  - For the left child of the right child (which is 'b'), increment the count for 'b' by 1.
  - For the right child of the right child (which is 'c'), increment the count for 'c' by 1.
Combine the counts from the children of the root node.
The cnt list represents the variable counts: cnt[a] = 1, cnt[b] = 1, and cnt[c] = 1.

For Tree 2:

Start at the root and call dfs with the root node (which contains '+').
Since the root node is '+', recur for the left and right child.
- For the left child (which contains '+'), recur for its children.
  - For the left child of the left child (which is 'b'), increment the count for 'b' by 1.
  - For the right child of the left child (which is 'a'), increment the count for 'a' by 1.
- For the right child (which is 'c'), there's no child, so increment the count for 'c' by 1.
Combine the counts from the children of the root node.
The cnt list represents the variable counts: cnt[a] = 1, cnt[b] = 1, and cnt[c] = 1.

After performing DFS on both trees:

counter from Tree 1: [1, 1, 1, 0, 0, ...., 0] (indices 0, 1, 2 correspond to 'a', 'b', 'c')
counter from Tree 2: [1, 1, 1, 0, 0, ...., 0] (indices 0, 1, 2 correspond to 'a', 'b', 'c')

Finally, we compare the counts from both trees:

Since the variable counts are identical for both trees ([1, 1, 1, 0, 0, ...., 0]), the function concludes by returning True, as the trees are equivalent in terms of their evaluation, fulfilling the objective of the task.

Solution Implementation

1class Node(object):
2    def __init__(self, val=" ", left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7class Solution:
8    def check_equivalence(self, root1: 'Node', root2: 'Node') -> bool:
9        """
10        This function checks if two given binary trees are equivalent based
11        on the expression tree equivalence rules.
12        """ 
13      
14        def depth_first_search(root):
15            """
16            Traverse the tree using depth-first search and counts the frequency
17            of non-operator characters.
18            """
19            count = [0] * 26  # Initialize the list to store the character frequency
20          
21            if root is None:
22                return count
23          
24            if root.val in '+-':  # If the node is an operator
25                # Recursively get the counts from left and right subtrees
26                left_count, right_count = depth_first_search(root.left), depth_first_search(root.right)
27                # If operator is '-', inverse the count of the right subtree
28                operator_factor = 1 if root.val == '+' else -1
29                # Combine counts from left and right subtrees according to the operator
30                for i in range(26):
31                    count[i] += left_count[i] + right_count[i] * operator_factor
32            else:
33                # If the node is a variable (non-operator), increment its count
34                count[ord(root.val) - ord('a')] += 1
35              
36            return count
37
38        # Use the helper function to get counts from both trees and compare
39        root1_count = depth_first_search(root1)
40        root2_count = depth_first_search(root2)
41      
42        # Two trees are equivalent if their counts match
43        return root1_count == root2_count
44

1/**
2 * Definition for a binary tree node.
3 */
4class Node {
5    char val;
6    Node left;
7    Node right;
8
9    Node() { this.val = ' '; }
10
11    Node(char val) { this.val = val; }
12
13    Node(char val, Node left, Node right) {
14        this.val = val;
15        this.left = left;
16        this.right = right;
17    }
18}
19
20class Solution {
21    /**
22     * Checks if two given binary expression trees are equivalent.
23     *
24     * @param root1 The root of the first binary expression tree.
25     * @param root2 The root of the second binary expression tree.
26     * @return true if the trees are equivalent, false otherwise.
27     */
28    public boolean checkEquivalence(Node root1, Node root2) {
29        int[] count1 = depthFirstSearch(root1);
30        int[] count2 = depthFirstSearch(root2);
31
32        // Compare the counts of each variable character
33        for (int i = 0; i < 26; ++i) {
34            if (count1[i] != count2[i]) {
35                return false;
36            }
37        }
38      
39        // If all counts match, the expressions are equivalent
40        return true;
41    }
42
43    /**
44     * Performs depth-first search on the binary expression tree
45     * and counts the occurrences of each variable character.
46     *
47     * @param root The root of the binary expression tree.
48     * @return An array containing the counts of each variable character.
49     */
50    private int[] depthFirstSearch(Node root) {
51        int[] count = new int[26]; // There are 26 possible lowercase English letters a-z.
52
53        // Base condition, if the node is null, return the count array.
54        if (root == null) {
55            return count;
56        }
57
58        // If the current node is an operator, calculate the counts from both subtrees.
59        if (root.val == '+' || root.val == '-') {
60            int[] leftCount = depthFirstSearch(root.left);
61            int[] rightCount = depthFirstSearch(root.right);
62            int factor = root.val == '+' ? 1 : -1; // Use 1 for addition and -1 for subtraction.
63          
64            // Combine the counts from left and right children.
65            for (int i = 0; i < 26; ++i) {
66                count[i] += leftCount[i] + rightCount[i] * factor;
67            }
68        } else {
69            // If the current node is not an operator, it's a variable.
70            // Increment the count for that character.
71            count[root.val - 'a']++;
72        }
73
74        return count;
75    }
76}
77

1#include <vector>
2#include <functional>
3using namespace std;
4
5// Definition for a binary tree node.
6struct Node {
7    char val;
8    Node *left;
9    Node *right;
10    Node() : val(' '), left(nullptr), right(nullptr) {}
11    Node(char x) : val(x), left(nullptr), right(nullptr) {}
12    Node(char x, Node *left, Node *right) : val(x), left(left), right(right) {}
13};
14
15class Solution {
16public:
17    bool checkEquivalence(Node* root1, Node* root2) {
18        // Define depth-first search (DFS) lambda function to traverse the tree.
19        // It returns the frequency count of variables as a vector of size 26.
20        function<vector<int>(Node*)> dfs = [&](Node* root) -> vector<int> {
21            vector<int> count(26); // Create a vector to hold the count of each variable ('a' to 'z').
22
23            // Base case: return an empty count vector if the root is null.
24            if (!root) {
25                return count;
26            }
27
28            // Check if the current node is an operator ('+' or '-').
29            if (root->val == '+' || root->val == '-') {
30                // Recursively traverse the left and right subtrees.
31                vector<int> leftCount = dfs(root->left);
32                vector<int> rightCount = dfs(root->right);
33              
34                // Since '-' operator is not valid for equivalence checking, we treat it same as '+'
35                // You may need to adjust logic here if the problem specification changes regarding '-' operator
36
37                // Merge counts from left and right subtrees.
38                for (int i = 0; i < 26; ++i) {
39                    count[i] = leftCount[i] + rightCount[i];
40                }
41            } else {
42                // If the current node is a variable, increment the corresponding count.
43                count[root->val - 'a']++;
44            }
45            return count; // Return the counts from both subtrees merged together.
46        };
47
48        // Compare the frequency counts returned by DFS from both trees.
49        return dfs(root1) == dfs(rhs(root2));
50    }
51};
52

1// Definition for a binary tree node
2interface TreeNode {
3  val: string;
4  left: TreeNode | null;
5  right: TreeNode | null;
6}
7
8/**
9 * Check whether two binary trees are equivalent.
10 * Two trees are considered equivalent if they sum up to the same
11 * frequency of each character (excluding the '+' character which
12 * represent tree nodes, not values).
13 * 
14 * @param {TreeNode} root1 - The root of the first tree
15 * @param {TreeNode} root2 - The root of the second tree
16 * @returns {boolean} - True if the trees are equivalent, otherwise false
17 */
18const checkEquivalence = (root1: TreeNode | null, root2: TreeNode | null): boolean => {
19  // Depth-First Search function to calculate the frequency of each character in the tree
20  const dfs = (root: TreeNode | null): number[] => {
21    const frequencyCount: number[] = new Array(26).fill(0);
22    if (!root) {
23      return frequencyCount;
24    }
25    if (root.val === '+' || root.val === '-') {
26      const leftSide = dfs(root.left);
27      const rightSide = dfs(root.right);
28      const factor = root.val === '+' ? 1 : -1;
29      for (let i = 0; i < 26; ++i) {
30        frequencyCount[i] = leftSide[i] + factor * rightSide[i];
31      }
32    } else {
33      const index = root.val.charCodeAt(0) - 'a'.charCodeAt(0);
34      frequencyCount[index]++;
35    }
36    return frequencyCount;
37  };
38
39  // Calculate frequency counts for both trees
40  const frequencyCount1 = dfs(root1);
41  const frequencyCount2 = dfs(root2);
42
43  // Compare the frequency counts for every character
44  for (let i = 0; i < 26; ++i) {
45    if (frequencyCount1[i] !== frequencyCount2[i]) {
46      return false;
47    }
48  }
49  return true;
50};
51

Time and Space Complexity

Time Complexity

The time complexity of the function is determined by the number of nodes in the binary trees since it has to traverse every node to evaluate the expression and count the variables. The traversal is a Depth-First Search (DFS), which visits each node exactly once. Therefore, if n represents the number of nodes in the larger tree of the two, the time complexity is O(n).

Space Complexity

The space complexity is composed of two parts: the space taken up by the recursion stack during the DFS and the space for the count arrays.

Recursion Stack: In the worst case, the binary tree might be completely unbalanced, resulting in a depth equal to the number of nodes n, which makes the maximum space used by the call stack O(n) in the worst case.
Count Arrays: The count arrays are of fixed size 26 (to keep track of occurrences of each letter 'a' to 'z'), but the function dfs creates a new count array for each node. However, these arrays do not exist simultaneously for all nodes at the same time. Only a number of arrays equal to the height of the tree will exist at any time during the execution of the traversal (equivalent to the depth of recursion). Thus, the space taken by count arrays is proportional to the height of the tree. In the worst case, this could be O(n), but for a balanced tree, it would be O(log n).

Considering the stack space and the variables, the overall space complexity in the worst case scenario will be O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan: