02
Intuition
Two trees are the same iff their roots match and both subtree pairs are the same — the definition is the recursion. Base cases: both empty (true), one empty (false).
03
Approach
1
Compare roots, recurse in parallel
p.val == q.val AND same(p.left, q.left) AND same(p.right, q.right).
2
Null logic first
Both None → True. Exactly one None → False. This catches structural mismatches before touching values.
3
Short-circuit
The and-chain stops at the first mismatch — no wasted traversal.
04
Solution & live demo
python
▶1class Solution:
▶2 def isSameTree(self, p, q):
▶3 if not p and not q: return True
▶4 if not p or not q: return False
▶5 return (p.val == q.val
▶6 and self.isSameTree(p.left, q.left)
▶7 and self.isSameTree(p.right, q.right))
05
Edge cases
Same values, different shape, e.g. [1,2] vs [1,null,2]
One side hits None-vs-node → False.
Both empty
Vacuously identical → True.
06
Complexity
Time
O(n)
Space
O(h)
Visits each pair once.