Same Tree (Check If Two Trees Are Identical)
WHAT IT SAYS
Given the roots of two binary trees, decide whether the trees are structurally identical with the same values at every position.
WHAT IT'S REALLY ASKING
"What does 'identical' even mean for trees? Try to define it without recursion — you can't. Two trees are the same when their roots match AND their left subtrees are the same AND their right subtrees are the same. Write that sentence down and you have already written the algorithm."
Serialise both trees and compare the strings
O(n) time, O(n) space for both serialisationsFlatten each tree into a string via a traversal — with null markers so that structure survives — and check whether the two strings are equal.
WHERE THE WORK IS WASTED — Two specific costs. First, the trap that makes this approach dangerous rather than just wasteful: serialise WITHOUT null markers and two differently-shaped trees can produce identical traversals — preorder [1,2] is both 'left child' and 'right child' — so the easy version of this idea is simply wrong, and the correct version needs care to prove. Second, even done right, it materialises both trees in full before comparing byte one. If the roots already differ, the answer was available after two reads — yet you built two O(n) strings to learn it. All the memory buys you nothing the direct walk didn't have.
Equality of trees is defined recursively — so test it recursively.
'Identical' for trees is not a primitive notion; it is built inductively, and the induction has exactly three clauses. Two empty trees are identical. An empty tree and a non-empty tree are not. Two non-empty trees are identical exactly when their root values match, their left subtrees are identical, and their right subtrees are identical. That is not an algorithm INSPIRED by the definition — it IS the definition, read as code. The recursion's structure and the concept's structure are the same object. When a property is defined by structural induction, the structurally-inductive checker is automatically correct; there is no gap between specification and implementation to put a bug in. Two consequences fall out and both matter in practice. First, the walk is a LOCKSTEP walk: one traversal advancing through two trees simultaneously, comparing position-for-position. Structure mismatches (one side null, the other not) and value mismatches are caught by the same three clauses — you never need to compare shapes and values separately, which is precisely the decomposition the serialisation approach struggles to get right. Second, failure short-circuits. The AND in the definition means the first mismatch anywhere settles the whole question — the recursion unwinds immediately, and on trees that differ early, the cost is the depth of the first difference, not the size of the trees. The serialisation approach pays O(n) unconditionally; the lockstep walk pays only until the first disagreement.
Lockstep recursion, three clauses
O(min(n, m)) time — it stops at the first mismatch — O(h) stack spaceIf both nodes are null, return true. If exactly one is null, return false. Otherwise return: values equal AND same(left, left) AND same(right, right). The two null-checks are doing the structural comparison; the value check and the two recursions do the rest.
Lockstep Walk
YOU'LL SEE IT AGAIN WHEN
- The property compares two structures position-for-position, so one traversal should advance through both simultaneously.
- The property's definition is itself a structural induction — base cases plus 'holds for the parts' — so the recursion writes itself.
- A single local mismatch settles the global answer, so short-circuiting makes the expected cost far below O(n).