🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires comparing two binary trees node by node. If both nodes are None
, they are the same. If only one of them is None
, they are not the same. If the values of the nodes are different, they are not the same. Otherwise, we need to check the left and right subtrees recursively.
Approach
- Base Case:
- If both
p
andq
areNone
, returnTrue
because two empty trees are the same. - If one ofp
orq
isNone
, or the values at the current nodes are different, returnFalse
. - Recursive Case:
- Recursively check the left subtrees of
p
andq
by callingisSameTree(p.left, q.left)
. - Recursively check the right subtrees ofp
andq
by callingisSameTree(p.right, q.right)
. - ReturnTrue
if both the left and right subtrees are the same, otherwise returnFalse
.
Complexity
Time Complexity:
O(N), where N is the number of nodes in the binary trees. Each node is visited once.
Space Complexity:
O(H), where H is the height of the tree. This is due to the space required for the recursion stack. In the worst case (for a completely unbalanced tree), the height is N, and in the best case (for a completely balanced tree), the height is log(N).
Code
C++
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) {
return true;
}
if (!p || !q || p->val != q->val) {
return false;
} else {
bool lSol = isSameTree(p->left, q->left);
if (lSol) {
return isSameTree(p->right, q->right);
} else {
return false;
}
}
}
};
Python
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
if not p or not q or p.val != q.val:
return False
else:
lSol = self.isSameTree(p.left, q.left)
if lSol:
return self.isSameTree(p.right, q.right)
else:
return False
Java
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null || p.val != q.val) {
return false;
} else {
boolean lSol = isSameTree(p.left, q.left);
if (lSol) {
return isSameTree(p.right, q.right);
} else {
return false;
}
}
}
}
JavaScript
var isSameTree = function (p, q) {
if (!p && !q) {
return true;
}
if (!q || !p || p.val != q.val) {
return false;
} else {
let lSol = isSameTree(p.left, q.left);
if (lSol) {
return isSameTree(p.right, q.right);
} else {
return false;
}
}
};