p13 — Same Tree

Source: LeetCode 100 · Easy · Topics: Tree, DFS, BFS, Binary Tree Companies (2024–2025 frequency): Amazon (high), Microsoft (high), Meta (high — almost always chained with LC 101/572), Bloomberg (medium), Google (medium), Apple (medium) Loop position: phone screen warmup; the canonical “function takes two trees” pattern.

1. Quick Context

This is the “parallel-walk-two-trees” template. The recursion takes TWO node arguments and walks both trees in lockstep. The base cases are subtle: both None → True; one None and other not → False; both non-None → compare values AND recurse on both pairs. This pattern generalizes to LC 101 (Symmetric — walk one tree against its own mirror), LC 572 (Subtree — same algorithm at every starting point), LC 951 (Flip-Equivalent — recurse with EITHER straight OR swapped child pairing), LC 1367 (Linked List in Binary Tree), and the whole tree-comparison family.

Mid candidates conflate the two None cases or miss the value check. Senior candidates write it cold with all four cases handled. Staff candidates note that this IS the template for LC 101 and LC 572, and offer the iterative version using paired-stack/queue.

What it looks like it tests: compare two trees. What it actually tests: can you reason about TWO recursion arguments simultaneously? Do you enumerate all base cases before coding?

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/same-tree/

STOP. 5-min timer. Code recursive AND iterative.

3. Prerequisite Concepts

• TreeNode + recursion fundamentals
• Boolean-returning recursion: True/False propagation rules
• Paired iteration (both queues advance together)
• Short-circuit evaluation: a and b and c stops at first False

4. How to Approach (FRAMEWORK Steps 1–9)

Step 1 — Restate: “Given roots of two binary trees, return True iff they are structurally identical AND every corresponding node has the same value.”

Step 2 — Clarify:

• “Both empty trees → True?” (Yes — vacuously identical.)
• “One empty, one not → False?” (Yes — different structure.)
• “Same structure, different values → False?” (Yes.)
• “Are nodes considered same if they’re the same object reference?” (Irrelevant — we compare structurally; same-reference would trivially be True.)
• “Max depth?” (LC says up to 100; production may be deeper.)

Step 3 — Constraints: N up to 100 per LC. O(N) time required (must compare every node in worst case where trees ARE equal). Recursion depth O(H).

Step 4 — Examples:

• [1,2,3] vs [1,2,3] → True.
• [1,2] vs [1,null,2] → False (structure differs).
• [1,2,1] vs [1,1,2] → False (values differ at children).
• Both [] → True.
• [1] vs [] → False.
• Same large random tree against deep-copy of itself → True.

Step 5 — Brute Force: Serialize both trees (any unambiguous traversal — e.g., level-order with None markers) and compare strings. O(N) time, O(N) space. Works but allocates extra strings/lists. Acceptable; recursive parallel walk is cleaner.

Step 6 — Complexity: O(min(N₁, N₂)) time when trees differ early (short-circuit); O(N) when equal. Space O(H) recursive or O(W) iterative.

Step 7 — Pattern Recognition: “Compare two trees in lockstep” → parallel recursion with two arguments. Iterative: paired queue (BFS) or paired stack (DFS).

Step 8 — Optimize: Already optimal. The “optimization” is early-exit via short-circuit (Python’s and does this for free).

Step 9 — Prove correctness: Induction on combined tree size. Base cases: (None, None) → True (both vacuous); (None, X) or (X, None) → False (different); both non-None with different values → False. Inductive case: both non-None, same value; trees are equal iff left subtrees are equal AND right subtrees are equal (each by hypothesis). By construction, the recurrence returns True iff both subtree comparisons return True AND values match.

5. Progressive Hints

If stuck for 5 min, open hints.md.

6. Deeper Insight — Why It Works

The four-base-case discipline: every “compare two trees” recursion must explicitly handle:

1. Both None → True (vacuous match)
2. p None, q not → False
3. p not, q None → False
4. Both non-None → compare values; if equal, recurse on both pairs

Conflating cases 2 and 3 into a single “one is None” check works (if p is None or q is None: return p is q) but is harder to read. Spelling all four explicitly is the Senior signal.

Why p is q for the “one-is-None” case: if both are None, the function returns True via case 1. If only one is None, p is q is False (None is not the same object as a TreeNode). So if p is None or q is None: return p is q correctly handles cases 1, 2, 3 in one line. Elegant but requires care.

Short-circuit and and: Python evaluates A and B and C left-to-right and stops at the first False. So node.val == other.val and is_same(left_pair) and is_same(right_pair) short-circuits on value mismatch (no wasted recursion). Production-relevant: comparison cost can be expensive (e.g., deep nested objects); ordering checks cheapest-first is a real optimization.

Iterative parallel walk:

q = deque([(p, q_root)])
while q:
    a, b = q.popleft()
    if a is None and b is None: continue
    if a is None or b is None or a.val != b.val: return False
    q.append((a.left, b.left))
    q.append((a.right, b.right))
return True

The queue holds PAIRS of nodes to compare. BFS is the natural form, but DFS-stack works identically (use .pop() instead of .popleft()). For early termination, DFS may finish faster on some inputs (depth-first hits a mismatch sooner if mismatch is deep on the first explored path).

Serialize-and-compare alternative: serialize(p) == serialize(q). O(N) time, O(N) space. Works but allocates the full serialization for both trees even when mismatch is at the root. Pure recursion short-circuits in O(1) on such inputs. State the trade-off.

Hash-and-compare (sketchy but tempting): hash(serialize(p)) == hash(serialize(q)). Same cost as serialize, plus risk of hash collision (extremely small for reasonable hash functions but not zero). Don’t recommend.

Connection to mirror-walk (LC 101, p15): Symmetric Tree = “compare a tree against itself with cross-recursion.” Same algorithm; only the recursion pairing changes — is_mirror(a, b) = a.val == b.val AND is_mirror(a.left, b.right) AND is_mirror(a.right, b.left). The cross (a.left ↔ b.right) is the mirror operator.

Connection to subtree (LC 572): “Is t a subtree of s?” = “Does t match s at any node?” = is_same(s, t) OR is_subtree(s.left, t) OR is_subtree(s.right, t). The recursion uses is_same as a building block.

7. Anti-Pattern Analysis

Wrong-but-tempting #1 — Forgetting one of the null cases:

def is_same(p, q):
    if p is None and q is None: return True
    return p.val == q.val and is_same(p.left, q.left) and is_same(p.right, q.right)

Crashes on p=None, q=Node(1) — accesses p.val on None.

Wrong-but-tempting #2 — Comparing only structure or only values:

return is_same(p.left, q.left) and is_same(p.right, q.right)

(Missing the p.val == q.val check.) Trees with same structure but different values incorrectly compared True.

Wrong-but-tempting #3 — p == q for the value compare on TreeNodes:

return p == q and is_same(...)  # WRONG

Without a custom __eq__, p == q defaults to p is q — identity, not value equality. Always p.val == q.val.

Wrong-but-tempting #4 — Serialize-and-compare with str concat in a loop:

def serialize(node):
    if node is None: return "N"
    return str(node.val) + serialize(node.left) + serialize(node.right)

Quadratic-time string concatenation (each + allocates new string). Use "".join([...]) or a list-then-join. But still O(N) space allocation — pure recursion is preferred.

Wrong-but-tempting #5 — Iterative version with two separate queues:

qa, qb = deque([p]), deque([q])
while qa and qb:
    a, b = qa.popleft(), qb.popleft()
    if a.val != b.val: return False
    qa.append(a.left); qa.append(a.right)
    qb.append(b.left); qb.append(b.right)
return not qa and not qb

Works but conflates None handling — if a.left=None and b.left=Node, both get appended, then we deref None on next iter. Use a SINGLE queue of pairs; cleaner and harder to get wrong.

8. Skills & Takeaways

Generalizable patterns:

• Parallel-walk-two-trees recursion — two arguments, four base cases.
• Boolean-AND recursion with short-circuit — order checks cheap-to-expensive.
• Paired queue/stack for iterative parallel walks.

Analogous problems:

• LC 101 — Symmetric Tree (p15): same algorithm, cross-recursion.
• LC 572 — Subtree of Another Tree: uses is_same as a sub-routine.
• LC 951 — Flip-Equivalent: recurse with EITHER straight OR swapped pairing.
• LC 1367 — Linked List in Binary Tree: parallel-walk a linked list and a tree.
• LC 617 — Merge Two Binary Trees: parallel-walk + construct new tree from pairs.

When NOT to use this: if you only need a hash for fast equality check (caching, deduplication), serialize-and-hash is fine and reusable. For one-off equality, the recursion is cleaner.

9. When to Move On

• Recursive in <3 min with all four base cases handled explicitly.
• Iterative with paired queue in <5 min.
• I can rewrite the four cases as a one-liner using p is q and explain why it’s correct.
• My stress_test() includes “same tree”, “different by structure”, “different by value”, deep-copy equality.
• I solved LC 572 (Subtree) and recognized is_same as a building block.
• I can sketch LC 101 (Symmetric) from this template by changing pairing.

10. Company Context

Meta (almost always asked as part of chain LC 100 → 101 → 572)

• The framing: “Are these two trees identical?” → “Now check symmetric.” → “Now check subtree.”
• What they want to hear: Recognize the template across all three. Pivot fluidly. Bonus for noting that LC 572 hashing variant (Merkle-tree-style) is O(N+M) vs naive O(N·M).

Amazon

• The framing: Often “are two version trees of an order identical?”
• Adversarial extension: “Now ignore certain fields (status, timestamp) in comparison.” (Custom value comparator.)
• What they want to hear: Clean base cases; abstracted value comparator function.

Microsoft / Apple / Bloomberg

• Standard problem. Clean code, all base cases, iterative on request.

Google

• Adversarial extension: “Implement using a Merkle hash so equality check is O(1) after preprocessing.” (Each node hashes its subtree; equality is hash compare. Trade-off: collision risk; need strong hash.)

11. Interviewer’s Lens

12. Level Delta

13. Follow-up Questions

Follow-up 1: “Iteratively.”

“Single queue of (a, b) pairs. Pop, check both-None (continue), one-None (False), val-mismatch (False); else enqueue (a.left, b.left) and (a.right, b.right). O(N), O(W).”

Follow-up 2: “Now check Symmetric Tree (LC 101).”

“Same algorithm, cross-recursion: is_mirror(a, b) = a.val == b.val AND is_mirror(a.left, b.right) AND is_mirror(a.right, b.left). Call as is_mirror(root.left, root.right). The cross-pairing IS the mirror.”

Follow-up 3: “Is t a subtree of s? (LC 572)”

“is_subtree(s, t) = is_same(s, t) OR is_subtree(s.left, t) OR is_subtree(s.right, t). O(N·M) worst case. Better: Merkle-hash both; subtree check becomes ‘does t’s hash appear among s’s subtree hashes?’ — O(N + M) after preprocessing.”

Follow-up 4: “Ignore values; only compare structure.”

“Drop the value check; keep the four base cases. Now same_structure(p, q) = (p is None) == (q is None) AND same_structure(p.left, q.left) AND same_structure(p.right, q.right). O(min(N,M)) short-circuit.”

Follow-up 5 (Principal signal): “How would Git’s tree-object equality work?”

“Each Git tree object is a list of (mode, name, blob/tree SHA) entries. Two trees are equal iff their SHA-1 hashes match. The hash is computed bottom-up: leaves (blobs) hash their content; trees hash their entry list (which includes children’s hashes). This is a Merkle tree: equality is O(1) after preprocessing, and partial-equality detection (which subtree changed) is O(log N) for balanced trees. The cost: O(N) preprocessing per tree. Worth it when comparisons are repeated (Git pull/push compare many trees against many trees).”

14. Full Solution Walkthrough

See solution.py. Five sections:

1. TreeNode + helpers (build_tree, random_tree, clone_tree)
2. is_same_recursive — explicit four-case handling
3. is_same_iterative — single queue of pairs
4. stress_test — 1000 trees: (a) identical clones expect True; (b) mutate one node and expect False
5. edge_cases — empty/empty, empty/single, val-mismatch, structure-mismatch

15. Beyond the Problem — Production Reality

Real applications:

• Git tree-object diffing — Merkle-hash-based.
• React virtual DOM reconciliation — pairs old and new VDOM trees, walks in parallel, applies minimal patches.
• Distributed config sync (etcd, Consul) — compare-and-swap on config trees; equality check on snapshots.
• AST equivalence checking in compilers (e.g., is this expression CSE-equivalent to that one?).
• Database schema diff tools (Liquibase, Flyway) — compare expected vs actual schema trees.

Production caveat — value equality may be expensive: if tree node values are deeply nested objects (e.g., JSON), value comparison itself is recursive. Ordering checks cheap-to-expensive (identity-then-hash-then-deep-equal) is the production pattern.

Principal-engineer code review comment: “Our config-tree equality check was O(N·D) where D = depth-of-each-value’s-nested-JSON. We were comparing 10MB configs across 100 services in a healthcheck loop = 1 GB/s comparison cost. Replaced with Merkle hashing at write time: equality check is now O(1) hash compare; rebuild hash only on write. Throughput went 1000×. Lesson: if you compare the same trees repeatedly, hash them once.”