100. Same Tree
Problem Description
The problem presents us with two binary trees and asks us to determine if they are the same. To be considered the same, every corresponding node in the two trees must have the same value and the same structure. This means that not only should the values of the nodes at the same positions match, but the shape of the trees must be identical as well. There should be no node in one tree that does not have a corresponding node in the same position of the other tree. This comparison should be consistent all the way down to the leaves of both trees.
Intuition
The intuition behind the solution to this problem involves recursion and understanding the nature of binary trees. Given two binary trees, the simplest case to compare them is when both trees are empty; they are obviously the same. The next step is to check the root nodes of both trees. If one is empty and the other is not, or if they have different values, then the trees are not the same.
However, if the root nodes match in value (and neither is None), we must then continue the comparison with their children. To do this, we apply the same comparison process to the left child of both trees and the right child of both trees.
This process is a typical example of a Depth-First Search (DFS) because it explores as far as possible along each branch before backtracking. In the provided solution, recursive function calls are made to compare the left children of p and q, and the right children of p and q, ensuring that each subtree is identical in both structure and value. This recursion continues until all nodes have been visited, or a mismatch is found.
This approach works efficiently since it has the ability to terminate early as soon as a mismatch is detected, without needing to check the rest of the tree.
Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.
What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?
Solution Approach
The solution to this problem uses a recursive Depth-First Search (DFS) pattern to explore both trees simultaneously. The DFS algorithm repeatedly explores a branch as deeply as possible before backtracking. This approach is implemented by recursively checking each node pair of both trees.
Let's walk through the implementation in the provided code:
- The base case checks if
pandqare bothNone. If both areNone, it means we've reached the end of both branches, the trees are identical so far, and we returnTrue. - The next base case checks if one of the trees is
Noneand the other is not, or if the current nodes' values do not match (p.val != q.val). Since the trees need to be structurally identical and have the same values, in these cases we returnFalse. - If none of the base cases terminate the function, the code proceeds to check both the left and right subtrees by calling
isSameTreerecursively forp.leftandq.left, and then forp.rightandq.right. - The return value is the result of joining these two boolean checks with an
andoperator. Theandoperator ensures that both subtrees (left and right) need to be identical for the function to returnTrue.
This recursion will "unravel" when it reaches the bottom of the trees (the leaves), at each stage combining the results from left and right comparisons until it reaches the initial call at the root. If all nodes are matched perfectly throughout the recursion, then the final result would be True, meaning both binary trees are the same.
The DFS pattern requires no additional data structures as it operates directly on the tree nodes and utilizes the system's call stack for its recursion.
Overall, the algorithm runs in O(n) time complexity where n is the number of nodes in the trees, as every node is visited once. The space complexity can be up to O(n) as well, particularly in the case of a completely unbalanced tree where a call stack proportionate to the number of nodes would be needed.
Depth first search is equivalent to which of the tree traversal order?
Example Walkthrough
Let's consider two small binary trees A and B as an example to illustrate the solution approach.
Tree A:
1 1 2 / \ 32 3
Tree B:
1 1 2 / \ 32 3
Both trees appear to be structurally identical and also have the same node values corresponding to each position, but we need to use our algorithm to confirm this.
We start our recursive function isSameTree and check the root nodes of both trees A and B. The roots of both trees have the value 1. Since neither is None and both values match, we proceed with the recursive checks on the children.
Next, we compare the left children of the two trees (A.left and B.left) which are 2 and 2. We call isSameTree(A.left, B.left):
- Since both values match and there are no more children to these nodes, the recursive call for these left children will eventually return
True.
Next, we move on to compare the right children of the two trees (A.right and B.right) which are 3 and 3. We call isSameTree(A.right, B.right):
- Again, since both values match and there are no further children, the recursive call for these right children will also return
True.
Since both recursive calls resulted in True, we continue by combining these two results with an and operator:
isSameTree(A.left, B.left) and isSameTree(A.right, B.right) which is True and True, resulting in True.
Finally, as we have no more nodes left to compare and all matched perfectly, the unraveled recursive calls return back to the initial call invoking the root nodes, confirming that Tree A and Tree B are indeed the same. The isSameTree function would, therefore, return True for these two trees.
Solution Implementation
1class TreeNode:
2 # TreeNode class definition
3 def __init__(self, val=0, left=None, right=None):
4 self.val = val # value of the node
5 self.left = left # left child
6 self.right = right # right child
7
8class Solution:
9 def isSameTree(self, tree1: Optional[TreeNode], tree2: Optional[TreeNode]) -> bool:
10 """
11 Checks if two binary trees are the same.
12
13 Args:
14 tree1 (Optional[TreeNode]): The root node of the first binary tree.
15 tree2 (Optional[TreeNode]): The root node of the second binary tree.
16
17 Returns:
18 bool: True if both trees are identical, False otherwise.
19 """
20
21 # If both trees are None, they are the same (both empty)
22 if tree1 == tree2:
23 return True
24
25 # If one of the trees is None or the values of current nodes are different,
26 # then the trees are not the same.
27 if tree1 is None or tree2 is None or tree1.val != tree2.val:
28 return False
29
30 # Otherwise, check recursively for the left and right subtrees.
31 # Both subtrees must be the same for the entire trees to be considered the same.
32 return self.isSameTree(tree1.left, tree2.left) and \
33 self.isSameTree(tree1.right, tree2.right)
341// Definition for a binary tree node.
2class TreeNode {
3 int val; // value of the node
4 TreeNode left; // left child
5 TreeNode right; // right child
6
7 // Constructor to create a new node with no children
8 TreeNode() {}
9
10 // Constructor to create a new node with a specified value
11 TreeNode(int val) {
12 this.val = val;
13 }
14
15 // Constructor to create a new node with a specified value and specified left and right children
16 TreeNode(int val, TreeNode left, TreeNode right) {
17 this.val = val;
18 this.left = left;
19 this.right = right;
20 }
21}
22
23class Solution {
24 public boolean isSameTree(TreeNode p, TreeNode q) {
25 // If both trees are empty, they are the same.
26 if (p == null && q == null) return true;
27
28 // If one of the trees is empty or the values of current nodes don't match,
29 // the trees aren't the same.
30 if (p == null || q == null || p.val != q.val) return false;
31
32 // Recursively check if the left subtree of both trees are the same
33 // AND the right subtree of both trees are the same.
34 return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
35 }
36}
371// Definition for a binary tree node.
2struct TreeNode {
3 int val; // Value of the node
4 TreeNode *left; // Pointer to the left child node
5 TreeNode *right; // Pointer to the right child node
6 // Constructor to initialize the node with a value. By default, left and right pointers are null.
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8 // Constructor to create a node with a value, left child, and right child.
9 TreeNode(int x, TreeNode *leftChild, TreeNode *rightChild) : val(x), left(leftChild), right(rightChild) {}
10};
11
12class Solution {
13public:
14 // Function to check if two binary trees are the same.
15 bool isSameTree(TreeNode* p, TreeNode* q) {
16 // If both nodes are the same instance or both are null, trees are the same.
17 if (p == q) return true;
18 // If one of the nodes is null or the values don't match, trees are not the same.
19 if (!p || !q || p->val != q->val) return false;
20
21 // Check recursively if left subtrees are the same and right subtrees are the same.
22 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
23 }
24};
251// Definition for a binary tree node.
2interface TreeNode {
3 val: number;
4 left: TreeNode | null;
5 right: TreeNode | null;
6}
7
8/**
9 * Determines if two binary trees are the same.
10 * Two binary trees are considered the same if they are structurally identical,
11 * and the nodes have the same values.
12 *
13 * @param {TreeNode | null} tree1 - The root node of the first binary tree.
14 * @param {TreeNode | null} tree2 - The root node of the second binary tree.
15 * @return {boolean} - True if both trees are the same, false otherwise.
16 */
17function isSameTree(tree1: TreeNode | null, tree2: TreeNode | null): boolean {
18 // Check if both nodes are null, which implies that we've reached the end of both trees.
19 if (tree1 === null && tree2 === null) {
20 return true;
21 }
22 // If one of the nodes is null or if the values of the nodes do not match, the trees aren't the same.
23 if (tree1 === null || tree2 === null || tree1.val !== tree2.val) {
24 return false;
25 }
26
27 // Recursively check the left and right subtrees.
28 return isSameTree(tree1.left, tree2.left) && isSameTree(tree1.right, tree2.right);
29}
30Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Time and Space Complexity
The time complexity of the given isSameTree function is O(N) where N is the number of nodes in the smaller of the two trees being compared. This occurs because the function is called recursively on each node of the trees until it either finds a discrepancy or checks all pairs of corresponding nodes.
The space complexity is O(log(N)) in the best case (balanced trees) due to the recursive stack, which would reach at most the depth of the tree. In the worst case (completely unbalanced trees), the space complexity would be O(N) since the recursive calls would occur in a linear fashion, leading to a call stack size equal to the number of nodes in the tree.
Learn more about how to find time and space complexity quickly using problem constraints.
Which technique can we use to find the middle of a linked list?
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
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.