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).
The template for comparing two trees in lockstep: recurse on both at once, and let the base cases carry all the work. Any structural question — same tree, symmetric tree, subtree of another tree — comes down to deciding what "both null", "one null", and "both present" should mean.
Approach
Compare roots, recurse in parallel
p.val == q.val AND same(p.left, q.left) AND same(p.right, q.right).
Null logic first
Both None → True. Exactly one None → False. This catches structural mismatches before touching values.
Short-circuit
The and-chain stops at the first mismatch — no wasted traversal.
Solution & live demo
Common pitfalls
Checking not p or not q before not p and not q
if not p or not q: return False if not p and not q: return True
if not p and not q: return True if not p or not q: return False
Two empty trees satisfy both conditions, so with the order reversed the first line fires and reports False for a pair of identical empty subtrees — which every leaf has two of. The order encodes the priority: agreement first, then mismatch.
Comparing values before checking for null
if p.val != q.val: return False
if not p and not q: return True if not p or not q: return False return p.val == q.val and ...
The moment either side runs out of nodes, p.val raises AttributeError. Structure has to be settled before values are read.
Edge cases
One side hits None-vs-node → False.
Vacuously identical → True.