Lesson 30 — Trees III: walking two trees at once

~20 minutes · Day 33 · simultaneous DFS

Tonight's interview move is small but important: sometimes one recursive call is not enough. In Same Tree, the question is not "what is the answer for one subtree?" It is "do these two current positions describe the same tree?" That means every step carries two nodes, not one.

The invariant

Two trees are identical iff their roots match and both pairs of subtrees are identical — compare them in lockstep.

That sentence is the whole pattern. Do not try to remember a special trick for Same Tree. Remember the lockstep question: compare the two current roots, then compare left with left and right with right.

Lockstep DFS keeps the two current positions together, so shape and values are checked at the same time.

Same Tree: the bulky way first

The blunt approach is serialize-and-compare: turn each tree into a preorder list with explicit null markers, then compare the two lists. That works because null markers preserve shape, but it spends O(n + m) extra space building two full representations before the comparison is finished. The problem statement gives two binary-tree roots, so we can compare those roots directly instead.

Same Tree: the lockstep way

A recursive DFS is a natural fit for trees: answer the question at this pair of nodes, then trust the same question on the paired children. Python's boolean operators also short-circuit, so the second subtree check is skipped if the first already proves failure (Python docs: boolean operations).

def isSameTree(p, q):
    if not p and not q:
        return True                  # both empty: same here
    if not p or not q:
        return False                 # one empty: shapes differ
    if p.val != q.val:
        return False                 # roots differ
    return (isSameTree(p.left, q.left) and
            isSameTree(p.right, q.right))  # paired children

The order matters. Empty-vs-empty is success. Empty-vs-node is failure. Two nodes with different values are failure. Only after those checks do the child pairs get a vote.

Transfer: same question, new costume

Symmetric Tree: is a tree a mirror of itself?

Before opening the reveal: what should the paired recursive calls compare? Say the two pairs out loud.

The helper still carries two nodes; only the pairing rule changes from same-side to mirror-side.

What the trade buys you

Worst-case time is still linear because matching trees must be fully checked. The win is cleaner reasoning, early failure on the first mismatch, and only the recursion stack instead of two stored traversals. Here h is the height of the recursion stack.

Practice — answer before you scroll past

if not p or not q:
    return True

Your move (Day 33)

Solve Same Tree tonight, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Predict: name the pattern, state the serialize-and-compare brute force, then state the lockstep invariant.
2. Attempt: write the three base checks before the child recursion.
3. Compare: watch the source below only after your attempt.
4. Encode: write the invariant from this page and the DFS-with-return-value template in your own words.