Given the roots of two binary trees p and q, return true if they are structurally identical and every corresponding node holds the same value.
Example
Input p = [1,2,3], q = [1,2,3]
Output true
Key Pointers
Two trees match only if the current nodes match and both subtrees match recursively — one mismatch anywhere fails the whole comparison.
Handle the None cases first: both None is a match, exactly one None is not.
This node-by-node comparison is the same building block "Subtree of Another Tree" is built on.
Step-by-Step Analysis
If both p and q are None, return True.
If exactly one of p or q is None, return False.
If p.val != q.val, return False.
Return isSameTree(p.left, q.left) and isSameTree(p.right, q.right).
Complexity
Time: O(min(n, m)) — Space: O(min(h_p, h_q))
Code
def isSameTree(p: TreeNode | None, q: TreeNode | None) -> bool:
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
Code Explanation
How the solution above works, piece by piece.
Both empty: identical at this position → True.
Exactly one empty: shapes differ → False.
Both present but values differ → False.
Otherwise both left subtrees and both right subtrees must match; and short-circuits on the first mismatch.
O(n) time for n nodes, O(height) stack.
Visual Walkthrough
Running it on p = [1, 2, 3], q = [1, 2, 3]:
The recursion walks both trees in lockstep (dotted lines): same position, same value, then the same check on the left children and on the right children.