Same Tree
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.
p = "1, 2, 3", q = "1, 2, 3"truedef is_same_tree(p, q):
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)function isSameTree(p, q) {
if (!p && !q) return true;
if (!p || !q) return false;
if (p.val !== q.val) return false;
return isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right);
}class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
if (p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true;
if (!p || !q) return false;
if (p->val != q->val) return false;
return isSameTree(p->left, q->left)
&& isSameTree(p->right, q->right);
}Explanation
Two trees are the "same" only if they match at every position — same shape and same values. The neat way to check this is recursion: a big problem (whole trees match?) becomes the same small problem on the children.
At each step we compare nodes p and q with three quick checks. If both are null, this spot matches — return true. If only one is null, the shapes differ — return false. If both exist but p.val != q.val, the values differ — return false.
If none of those bail out, the current nodes agree, so we recurse: the trees match only if the left subtrees match and the right subtrees match.
Example: p = [1, 2, 3] and q = [1, 2, 3]. Roots both 1 — match, recurse. Left children both 2, right children both 3, and their children are all null pairs, so every branch returns true and the answer is true.
Each node pair is checked once, and the recursion naturally stops the moment any mismatch appears.