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.
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 usingreturn 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 returnsFalse
.
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 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
1 Tree 1 Tree 2
2 + +
3 / \ / \
4 a + + c
5 / \ / \
6 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
, andcnt[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.
- For the left child (which contains '+'), recur for its children.
- Combine the counts from the children of the root node.
- The
cnt
list represents the variable counts:cnt[a] = 1
,cnt[b] = 1
, andcnt[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 returningTrue
, 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 stackO(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 beO(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.
A heap is a ...?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
Got a question?Ā Ask the Monster AssistantĀ anything you don't understand.
Still not clear? Ā SubmitĀ the part you don't understand to our editors. Or join ourĀ Discord and ask the community.