How does a simultaneous recursion over two binary trees decide that they are identical?

## Comparing structure, not contents Asking whether two binary trees are *identical* means asking about two things at once: the same shape and the same keys in the same positions. A comparison that only looks at the keys answers a weaker question, and the gap between the two is exactly where restore-verification bugs live. ### The lockstep recursion ``` identical(p, q): if p == empty and q == empty: return true if p == empty or q == empty: return false if p.key != q.key: return false return identical(p.left, q.left) and identical(p.right, q.right) ``` The **order of the base cases matters**. The both-empty case must come first, because it is the only agreement terminal. The exactly-one-empty case is the structural check: it fires when one tree has a child where the other has nothing, which is the only way shape difference can show up locally. Only after both positions are known to be occupied is comparing keys meaningful. Time is O(min(n, m)) — the walk stops as soon as one side runs out or a mismatch appears, so it never visits more nodes than the smaller tree holds. Auxiliary space is O(h) for the call stack, which is O(n) in the degenerate case; an explicit stack of node pairs gives the same traversal iteratively when depth is a concern. Short-circuiting matters in practice: a mismatch near the root ends the comparison after a handful of comparisons, while two identical million-node trees genuinely cost a full traversal. ### Why key-sequence comparison is not enough Suppose a service snapshots an in-memory tree, restores it elsewhere, and verifies the restore by comparing a checksum of the two trees' inorder key sequences. That check passes for a restore that rebuilt a *balanced* tree from the same keys — the key multiset is identical and, for a search tree, so is the inorder sequence, because inorder of any valid search tree over a key set is just those keys sorted. The shapes are completely different. If the shape is meaningless (a pure lookup index) that is fine. If the shape carries meaning — evaluation order, per-node metadata, a path used in an audit record — the verification passed on a restore that lost information. The structural comparison catches it because it walks positions, not values. The general lesson: value-order agreement is a *necessary* consequence of identity, never a *sufficient* witness of it. ### The mirror variant A tree is symmetric when its left subtree is the mirror image of its right. That is the same recursion with the child pairing crossed: ``` mirror(p, q): ... same three base cases ... return mirror(p.left, q.right) and mirror(p.right, q.left) ``` and symmetry of a single tree is `mirror(root.left, root.right)`. Note what does **not** work: comparing a tree's inorder sequence with its reverse. Reversal agreement is necessary but not sufficient, for exactly the reason above — it constrains the values, not the positions. ### Containment: is one tree a subtree of another? The direct method runs the identity check at every host node whose key matches the candidate's root, giving O(n·m) in the worst case — a host that is a long chain of one repeated key and a candidate that agrees for m-1 levels before failing is the shape that realises it. The faster method serialises both trees with explicit empty-child markers and asks whether the candidate's encoding appears as a contiguous block of the host's, which a linear-time string matcher such as KMP answers in O(n+m). Two conditions make that sound: the markers must be present, so that the encoding determines the shape uniquely, and the tokens must be delimited, or the key 2 will appear to match inside the key 12 and manufacture a false hit. ### When comparisons repeat If the same trees are compared many times, hash each subtree bottom-up as a function of its key and its two children's hashes. Two subtrees are then compared in O(1) after an O(n) preprocessing pass, which is what makes repeated diffing of large trees affordable. The tradeoff is the usual one for fingerprinting: equal hashes are strong evidence, not proof, so a collision-sensitive use should confirm a hash match with a real structural walk.