Same Tree
Same Tree: are two binary trees structurally identical with equal values?
- The number of nodes in both trees is in the range [0, 100].
- -10⁴ <= Node.val <= 10⁴
Intuition
Two binary trees are the same tree when they have identical structure and identical values at every corresponding position. The useful observation is that this definition is already recursive, so the code barely has to do any thinking of its own.
Ask what it takes for two trees to match at the root. Three things have to hold at once: the root values are equal, the left subtrees are the same, and the right subtrees are the same. Each of those last two is the original question asked about a smaller tree — which means the recursion is not a clever trick you invented, it is the definition transcribed.
What deserves real care is the empty cases, because that is where structural differences are actually detected:
- Both nodes null means this position matches — two absent subtrees are identical, so return true.
- Exactly one node null means the trees differ in shape, so return false immediately.
Get those two backwards or collapse them into one check and the function will happily report that a three-node tree matches a one-node tree. The value comparison alone never catches a shape mismatch; the null handling is what does. Once those cases are right, the rest is a single and chain, and short-circuit evaluation stops the traversal the moment any mismatch is found.
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
Before reading on: price up what plain recursion costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(h) space.
Handle two nulls before anything else
If both p and q are null, you have run off the bottom of both trees at the same position. That is a match, so return true. This case has to come first, because the next check would otherwise treat it as a mismatch.
Handle one null as a definite mismatch
If exactly one of p and q is null, the trees have different shapes at this position, so return false. Writing it as if not p or not q: return False works only because the both-null case already returned — a good example of order mattering in base cases.
Compare the values at this position
With both nodes known to exist, compare p.val and q.val. Any difference means the trees are not the same and you can return false without touching either subtree. This is the only place actual data is examined.
Recurse on both sides and require both to hold
Return same(p.left, q.left) and same(p.right, q.right). Note that left is paired with left and right with right — pairing left against right would be testing for mirror symmetry, which is a different problem. The and means a single mismatch anywhere propagates all the way up as false.
Let short-circuiting stop the work early
Because and stops at the first false, a mismatch near the root ends the traversal immediately rather than exploring the rest of the tree. On trees that differ early this is dramatically faster than the worst case, though it does not change the asymptotic bound.
Cost when the trees do match
If the trees are identical, every node is visited exactly once, giving O(n) time where n is the node count of one tree. Space is O(h) for the recursion stack — O(log n) on a balanced tree, and O(n) on a degenerate chain, which is the case worth mentioning if an interviewer asks about stack depth.
The iterative version if recursion is off the table
Push the pair (p, q) onto a stack, then repeatedly pop a pair, apply the same three checks, and push the two child pairs. It carries the same complexity and is worth knowing when recursion depth is a stated constraint.
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.