p13 Same Tree — Progressive Hints

Rule: ONE hint at a time, 5-min timer.

Hint 1 — Pattern

The function takes TWO trees. Think about the recursive shape: at any pair (p, q), what must be true for the subtrees rooted there to be equal?

Hint 2 — Enumerate base cases

Write down ALL cases before coding:

p None AND q None → ?
p None AND q not None → ?
p not None AND q None → ?
Both non-None → ?

(Answers: True, False, False, recurse.)

Hint 3 — Recurrence for case 4

When both non-None, what conditions must hold? (a) values match; (b) left subtrees match; (c) right subtrees match. All three. Use and.

Hint 4 — Pseudocode

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

Iterative (BFS): single queue of PAIRS.

queue = deque([(p, q)])
while queue:
    a, b = queue.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
    queue.append((a.left, b.left))
    queue.append((a.right, b.right))
return True

Hint 5 — Full + traps

Time O(N), space O(H) recursive or O(W) iterative.

Trap 1 — Skipping a None case: missing case 2 or 3 crashes on p.val when p is None. Enumerate all four EXPLICITLY.

Trap 2 — Using p == q: without __eq__, this is identity check; not what you want. Always p.val == q.val.

Trap 3 — Iterative with two separate queues: they desync when one tree has None where the other has a node. Use a SINGLE queue of pairs.

Trap 4 — Returning early on val match: the and chain handles short-circuit; don’t write if p.val != q.val: return False followed by separate recursion calls — same logic, more lines.

Family preview:

LC 101 Symmetric Tree (p15) = same template, cross-recurse is_mirror(a.left, b.right) AND is_mirror(a.right, b.left).
LC 572 Subtree = is_same(s, t) OR is_subtree(s.left, t) OR is_subtree(s.right, t).

Internalize the parallel-walk template.