Same Tree — The Twin Topiaries

Boss 5: The Twin Topiaries

A short boss, on purpose. Its one new idea, recursing on two trees in lockstep, needs to sit alone for a moment, because the next boss builds a bigger machine around it and you'll want this part to already feel boring.

The story

The Grandview Hotel ordered twin topiaries for its twin gates. The contract is blunt: identical. Not "equally beautiful". Identical: the same branching structure, and the same plant at every position.

   Tree A          Tree B
   Boxwood         Boxwood
    /    \          /    \
  Holly  Yew     Holly   Yew

Identical. But:

   Tree A          Tree B
   Boxwood         Boxwood
    /                  \
  Holly               Holly

Same three plants, same count, and not identical: A branches left where B branches right. Shape counts. And:

   Tree A          Tree B
   Boxwood         Boxwood
    /    \          /    \
  Holly  Yew     Holly  Rose

One plant differs. Rejected.

The head gardener's inspection protocol: stand before both trunks simultaneously. Three possible situations at any pair of positions:

1. Both empty (no branch here on either tree): fine, move on. Emptiness matches emptiness.
2. One empty, one growing, or different plants: contract violated, stop everything.
3. Both growing, same plant: promising, now send inspectors down both lefts together and both rights together.

The problem, dressed up properly

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

LeetCode 100.

The naive attempt

Serialize both trees to lists via a traversal, compare the lists. The bug is instructive: a plain traversal (say, collect values in-order) throws away shape. The two lopsided boxwood-holly trees above produce identical value lists from different structures. You can patch this by recording None markers for missing children, and that patched version is actually legitimate (it returns in Boss 15!). But it does two full walks plus a comparison, with extra memory, to answer a question the lockstep walk answers in one.

The weapon: one function, two pointers, three cases

The gardener's protocol is the code. Walk both trees with one recursion holding a node from each:

The case order carries the logic. "Both None" must be tested before "one None", because the second test assumes the first failed. Get the ladder right and the function is impossible to write incorrectly; get it wrong and every bug is a None dereference.

def is_same_tree(p: TreeNode | None, q: TreeNode | None) -> bool:
    if not p and not q:
        return True                     # emptiness matches emptiness
    if not p or not q or p.val != q.val:
        return False                    # shape or plant mismatch
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

Three lines of cases, one line of lockstep descent. The and short-circuits: the first mismatch anywhere stops the inspection, right branches unvisited, exactly like the gardener walking off the job.

Watching it work

The shape-mismatch pair: A has Holly on the left, B has Holly on the right.

same(Boxwood_A, Boxwood_B)   values match → descend
├─ same(Holly, None)         one empty → FALSE
└─ (right pair never visited, short-circuit)

verdict: not the same ✓

Two comparisons total. The protocol fails fast and loudly, which is precisely what you want from a contract inspection.

Gotchas

1. p.val == q.val before the None checks. Dereferencing before verifying both exist. The case ladder exists to make this impossible, respect its order.

2. Comparing values only. The naive attempt's disease: any check that could pass the two lopsided-but-same-values trees is broken. Shape is half the contract, and shape lives in the pattern of Nones.

3. or instead of and on the descent. "Left sides match OR right sides match" approves half-identical topiaries. The hotel's lawyers will find you.

4. Overbuilding. This function is four lines. If yours has queues, flags, or helper classes, you've imported machinery the problem didn't order. Small bosses deserve small kills.

Complexity

Every pair of positions visited at most once.

Time: O(min(n, m)). Space: O(min(h_p, h_q)) for the lockstep stack.

Boss down. XP gained.

Both topiaries pass, position by position, and the twin gates get their twins.

What you walked away with:

• Lockstep recursion: one function advancing through two trees simultaneously
• The three-case ladder: both empty / mismatch / descend both sides, in that exact order
• Emptiness is information: None matching None is a passing check, not an edge case
• Short-circuit and as free early termination

Now, the reason this boss came fifth: what if the twin isn't standing at the gate, but hiding somewhere inside a bigger garden?

Next up: Boss 6 — The Hedge Stamp. A landscape designer suspects a rival stamped her signature hedge pattern somewhere inside his sprawling estate garden. Today's same() becomes the inner loop of a search: try every position in the big tree as a potential trunk, and run the twin inspection at each. Two recursions, nested, and a complexity conversation worth having out loud.