Problem Statement:
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.
Examples:
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 the tree is in the range
[0, 100]. -104 <= Node.val <= 104
Approach
- Base Case:
- If both nodes are
null, they are the same – returntrue. - If one is
nulland the other is not – returnfalse.
- If both nodes are
- Recursive Case:
- Check if current nodes have the same value.
- Recursively check their left subtrees and right subtrees.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Function Call: isSameTree(p, q) where
p = TreeNode(1)
├── left: TreeNode(2)
└── right: TreeNode(3)
q = TreeNode(1)
├── left: TreeNode(2)
└── right: TreeNode(3)
Step 1:
→ p = 1, q = 1
→ Both nodes are not null → OK
→ Compare p.val (1) == q.val (1) →
→ Recursively call isSameTree(p.left, q.left)
Step 2:
→ p = 2, q = 2
→ Both nodes are not null → OK
→ Compare p.val (2) == q.val (2) →
→ Recursively call isSameTree(p.left, q.left)
Step 3:
→ p = null, q = null
→ Both nodes are null → Return true
→ Back to Step 2, now call isSameTree(p.right, q.right)
Step 4:
→ p = null, q = null
→ Both nodes are null → Return true
→ Back to Step 2 → Left and Right both returned true → Return true
→ Back to Step 1, now call isSameTree(p.right, q.right)
Step 5:
→ p = 3, q = 3
→ Both nodes are not null → OK
→ Compare p.val (3) == q.val (3) →
→ Recursively call isSameTree(p.left, q.left)
Step 6:
→ p = null, q = null
→ Both nodes are null → Return true
→ Back to Step 5, now call isSameTree(p.right, q.right)
Step 7:
→ p = null, q = null
→ Both nodes are null → Return true
→ Back to Step 5 → Left and Right both returned true → Return true
→ Back to Step 1 → Left and Right both returned true → Return true
Final Result: true
p = TreeNode(1)
├── left: TreeNode(2)
└── right: TreeNode(3)
q = TreeNode(1)
├── left: TreeNode(2)
└── right: TreeNode(3)
Step 1:
→ p = 1, q = 1
→ Both nodes are not null → OK
→ Compare p.val (1) == q.val (1) →
→ Recursively call isSameTree(p.left, q.left)
Step 2:
→ p = 2, q = 2
→ Both nodes are not null → OK
→ Compare p.val (2) == q.val (2) →
→ Recursively call isSameTree(p.left, q.left)
Step 3:
→ p = null, q = null
→ Both nodes are null → Return true
→ Back to Step 2, now call isSameTree(p.right, q.right)
Step 4:
→ p = null, q = null
→ Both nodes are null → Return true
→ Back to Step 2 → Left and Right both returned true → Return true
→ Back to Step 1, now call isSameTree(p.right, q.right)
Step 5:
→ p = 3, q = 3
→ Both nodes are not null → OK
→ Compare p.val (3) == q.val (3) →
→ Recursively call isSameTree(p.left, q.left)
Step 6:
→ p = null, q = null
→ Both nodes are null → Return true
→ Back to Step 5, now call isSameTree(p.right, q.right)
Step 7:
→ p = null, q = null
→ Both nodes are null → Return true
→ Back to Step 5 → Left and Right both returned true → Return true
→ Back to Step 1 → Left and Right both returned true → Return true
Final Result: true
var isSameTree = function(p, q) {
if(!p && !q) return true;
if(!p || !q) return false;
return p.val === q.val &&
isSameTree(p.left, q.left) &&
isSameTree(p.right, q.right);
};
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isSameTree(p, q):
if not p and not q:
return True
if not p or not q:
return False
return p.val == q.val and \
isSameTree(p.left, q.left) and \
isSameTree(p.right, q.right)
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
return p.val == q.val &&
isSameTree(p.left, q.left) &&
isSameTree(p.right, q.right);
}
}
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
};
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true;
if (!p || !q) return false;
return p->val == q->val &&
isSameTree(p->left, q->left) &&
isSameTree(p->right, q->right);
}
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
int isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return 1;
if (!p || !q) return 0;
return (p->val == q->val) &&
isSameTree(p->left, q->left) &&
isSameTree(p->right, q->right);
}
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
}
public class Solution {
public bool IsSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
return p.val == q.val &&
IsSameTree(p.left, q.left) &&
IsSameTree(p.right, q.right);
}
}
