100. Same Tree -LeetCode(Python)
I got you!
Problem:
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: trueExample 2:
Input: p = [1,2], q = [1,null,2]
Output: falseExample 3:
Input: p = [1,2,1], q = [1,1,2]
Output: falseConstraints:
- The number of nodes in both trees is in the range
[0, 100]. -104 <= Node.val <= 104
Solution:
1. Recursive —
Explanation —
We can easily solve this problem using a depth-first search (DFS) algorithm.
The base case of our recursion is when we have reached the leaf nodes at both the trees, in which case we return True, because the path terminated at the same time.
If, however, only either of the tree paths has been terminated or the value at present nodes in both the trees is not the same, we return False.
Finally, we call our function recursively on both the left and right subtrees and return the value of their AND operation.
Time and Space Complexity —
Since we are visiting all nodes in the tree a constant number of times, we can say that our algorithm requires a linear amount of time to run.
Also, the recursion stack could be storing all nodes in the tree in case of a really skewed tree (like a linked list). So, we assume the space complexity to be linear in the worst case.
Thus, if m and n are the number of nodes in the given binary trees,
Time Complexity: O(m+n)
Space Complexity: O(m+n)
2. Iterative —
Explanation —
We could also use a breadth-first search (BFS) traversal algorithm.
We use a queue to store elements level wise from our trees.
At every step, we pop an element from the queue, which is just a pair of corresponding nodes in both the trees.
We then check if these nodes contain the same value. If yes, we append left children and right children of both the nodes as pairs into our queue.
If, however, we come across a pair that isn’t equal, we immediately return False.
The while loop terminates when all nodes in the tree have been traversed. So, now we can return True because no illegal pair was found while the BFS traversal.
Time and Space Complexity —
Since we are visiting each node in the tree only a constant number of times, we can say that our algorithm requires linear amount of time to run.
Also, our queue will be storing a maximum of (n / 2) nodes when it reaches the final level. So, we assume the space complexity to be linear in the worst case.
Thus, if m and n is the number of nodes in the trees,
Time Complexity: O(m+n)
Space Complexity: O(m+n)
