In this guide, you will get 100. Same Tree LeetCode Solution with the best time and space complexity. The solution to Same Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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: true
Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false
Example 3:
Input: p = [1,2,1], q = [1,1,2]
Output: false
Constraints:
The number of nodes in both trees is in the range [0, 100].
-104 <= Node.val <= 104
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(h)
100. Same Tree LeetCode Solution in C++
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p || !q)
return p == q;
return p->val == q->val && //
isSameTree(p->left, q->left) && //
isSameTree(p->right, q->right);
}
}; /* code provided by PROGIEZ */
100. Same Tree LeetCode Solution in Java
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null || q == null)
return p == q;
return p.val == q.val && //
isSameTree(p.left, q.left) && //
isSameTree(p.right, q.right);
}
} // code provided by PROGIEZ
100. Same Tree LeetCode Solution in Python
class Solution:
def isSameTree(self, p: TreeNode | None, q: TreeNode | None) -> bool:
if not p or not q:
return p == q
return (p.val == q.val and
self.isSameTree(p.left, q.left) and
self.isSameTree(p.right, q.right)) # code by PROGIEZ
