In a drawn game-search tree, how do you tell that different move orders re-explore the same position?

seniorshould knowfreq 56%

answer

What goes inside each node, exactly?
Label by arguments, not by the move
Look for two nodes reading the same
Equal labels mean identical subtrees
Check nothing outside the label is used

basics

~20 s

Label every node with the arguments the invocation received — the position and the remaining depth — instead of with the move that led there. Repeated labels are repeated work: identical labels have identical subtrees beneath them.

solid answer

~50 s

Stop labelling nodes by path and start labelling them by state. In an exploration that recurses on (position, remaining depth), two nodes carrying the same pair have byte-for-byte identical subtrees below them, no matter which move order reached them. Circle a few and you have measured your redundancy on the whiteboard: a tree that looks like 3^d nodes may cover far fewer distinct labels, because different move orders converge on the same position. That observation is what tells you a lookup keyed by state — not by path — would pay, and it is worth checking before you attempt any such fix. Two conditions must hold before you trust it: the result must depend only on the label, so any hidden history such as a repetition rule or a move counter must be folded into the label; and the number of distinct labels must actually be small enough to be worth holding.

Stop labelling nodes by path and start labelling them by state. In an exploration that recurses on `(position, remaining depth)`, two nodes carrying the same pair have byte-for-byte identical subtrees below them, no matter which move order reached them. Circle a few and you have measured your redundancy on the whiteboard: a tree that looks like 3^d nodes may cover far fewer distinct labels, because different move orders converge on the same position. That observation is what tells you a lookup keyed by state — not by path — would pay, and it is worth checking before you attempt any such fix. Two conditions must hold before you trust it: the result must depend only on the label, so any hidden history such as a repetition rule or a move counter must be folded into the label; and the number of distinct labels must actually be small enough to be worth holding.

code

pseudocode · 8 lines

pseudocode

explore(position, depth):
    if depth == 0:
        return evaluate(position)
    total = 0
    for m in moves(position):        // 3 candidate moves
        child = apply(position, m)
        total = total + explore(child, depth - 1)
    return total

go deeper

for a junior

Know that a node in a recursion tree is labelled by the arguments of that call, and that two nodes with the same arguments compute exactly the same thing.

for a middle

Explain why identical labels imply identical subtrees, and why the remaining depth belongs in the label alongside the position.

for a senior

Demonstrate the checks before acting: name every input the recursion truly depends on, catch in-place mutation that breaks the model, and estimate how widespread the repetition really is.

for a principal

Own the call on whether exploiting the repetition is worth it — memory ceiling for stored results, the correctness risk of an incomplete key, and whether the team can maintain the extra machinery.

The reading that matters

Most people draw a search tree with edges labelled by moves and nodes labelled by nothing in particular. That drawing shows the shape of the search but hides its most important property. Relabel every node with the arguments its invocation received — here the pair (position, remaining depth) — and a different fact surfaces: which nodes are actually the same computation.

The rule is simple and absolute for a function whose result depends only on its arguments: equal labels have identical subtrees. Same shape, same node count, same result. So circling two identically labelled nodes is circling duplicated work, and doing that across the drawing is a redundancy measurement, done by hand, before writing any code.

Two trees that look the same and are not

Draw two three-way branching trees of the same depth and they are visually indistinguishable. Under the labels they can be opposites.

Move orders converge. In many turn-based games, playing move A then move B reaches the same position as B then A. Those two nodes carry the same label, so one of the two subtrees below them is pure repetition. The deeper the search, the more such convergences accumulate, and the further the true count of distinct positions falls below the node count of the drawn tree.
Move orders diverge. In a game where every move permanently changes the board in an order-dependent way, no two sequences reach the same position. Every node carries a distinct label. The tree is exactly as expensive as it looks, and no amount of caching will make it cheaper — the only levers left are pruning and the depth cap.

The naive Fibonacci call tree is the extreme case of the first kind: it recurses on a single small integer, so the label space is tiny while the tree is exponential, and the same handful of labels appear over and over. A recursion that splits a range into two disjoint halves is the extreme case of the second: every invocation owns a slice nobody else touches, so no label ever repeats.

Why this is a senior reading and not a junior one

Because the two conditions that make the observation actionable are the ones that go wrong in production.

Condition one: the label must be complete. If the outcome depends on anything not in the label, then two nodes that look identical are not. Hidden dependencies in real search code include the history of the game so far (repetition or draw rules), a move counter, a clock, or a mutable board object that the recursion edits in place rather than copying. The last one is especially nasty — it makes a node's result depend on the order calls happened to run in, so the tree you drew is not the computation that ran. Before you claim two nodes are duplicates, name every input the invocation actually depends on and check that all of them are in the label.

Condition two: the distinct labels must be few. The whole point of circling repeats is that the number of distinct labels is much smaller than the number of nodes. If they are close, there is nothing to exploit, and any scheme for storing results costs memory and lookup time for no saving. "There is one duplicate on my whiteboard" is not evidence; estimate the label space and the convergence rate before committing.

When both conditions hold, the drawing has told you something concrete: results keyed by state can be reused across the tree, and the search stops paying for its own repetition. That is where this reading hands off — the drawing identifies the opportunity; sizing and implementing the reuse is a separate piece of work.

Doing it at the whiteboard

A practical routine, in the order an interviewer wants to hear it:

Write the recursion's parameter list. That tuple is the node label.
Expand two or three levels and write the label inside each node, not on the edges.
Scan for repeats. Circle a repeated pair and say out loud that their subtrees are identical.
Ask what else the result depends on that is not in the label — and if something is, either add it to the label or admit the nodes are not duplicates.
Say whether the distinct-label count looks small relative to the node count. That is the finding.

A candidate who does steps 1 through 3 is competent. A candidate who volunteers step 4 unprompted is the one who has debugged a search that returned different answers on different runs.

Common traps

Labelling by path instead of by state. Then no two nodes ever look equal and the redundancy is invisible.
Assuming visual similarity means duplication. Two subtrees of the same shape are not the same computation unless their labels match.
Forgetting the depth argument. The same position with different remaining depth is a different label and a different subtree.
Ignoring in-place mutation. A recursion that edits shared state makes the tree unreliable as a model of what actually ran.
Declaring a win from one circled pair. Redundancy has to be widespread to be worth exploiting.

## The reading that matters Most people draw a search tree with edges labelled by moves and nodes labelled by nothing in particular. That drawing shows the *shape* of the search but hides its most important property. Relabel every node with the arguments its invocation received — here the pair `(position, remaining depth)` — and a different fact surfaces: which nodes are actually the same computation. The rule is simple and absolute for a function whose result depends only on its arguments: **equal labels have identical subtrees**. Same shape, same node count, same result. So circling two identically labelled nodes is circling duplicated work, and doing that across the drawing is a redundancy measurement, done by hand, before writing any code. ## Two trees that look the same and are not Draw two three-way branching trees of the same depth and they are visually indistinguishable. Under the labels they can be opposites. - **Move orders converge.** In many turn-based games, playing move A then move B reaches the same position as B then A. Those two nodes carry the same label, so one of the two subtrees below them is pure repetition. The deeper the search, the more such convergences accumulate, and the further the true count of distinct positions falls below the node count of the drawn tree. - **Move orders diverge.** In a game where every move permanently changes the board in an order-dependent way, no two sequences reach the same position. Every node carries a distinct label. The tree is exactly as expensive as it looks, and no amount of caching will make it cheaper — the only levers left are pruning and the depth cap. The naive Fibonacci call tree is the extreme case of the first kind: it recurses on a single small integer, so the label space is tiny while the tree is exponential, and the same handful of labels appear over and over. A recursion that splits a range into two disjoint halves is the extreme case of the second: every invocation owns a slice nobody else touches, so no label ever repeats. ## Why this is a senior reading and not a junior one Because the two conditions that make the observation actionable are the ones that go wrong in production. **Condition one: the label must be complete.** If the outcome depends on anything not in the label, then two nodes that look identical are not. Hidden dependencies in real search code include the history of the game so far (repetition or draw rules), a move counter, a clock, or a mutable board object that the recursion edits in place rather than copying. The last one is especially nasty — it makes a node's result depend on the order calls happened to run in, so the tree you drew is not the computation that ran. Before you claim two nodes are duplicates, name every input the invocation actually depends on and check that all of them are in the label. **Condition two: the distinct labels must be few.** The whole point of circling repeats is that the number of distinct labels is much smaller than the number of nodes. If they are close, there is nothing to exploit, and any scheme for storing results costs memory and lookup time for no saving. "There is one duplicate on my whiteboard" is not evidence; estimate the label space and the convergence rate before committing. When both conditions hold, the drawing has told you something concrete: results keyed by state can be reused across the tree, and the search stops paying for its own repetition. That is where this reading hands off — the drawing identifies the opportunity; sizing and implementing the reuse is a separate piece of work. ## Doing it at the whiteboard A practical routine, in the order an interviewer wants to hear it: 1. Write the recursion's parameter list. That tuple *is* the node label. 2. Expand two or three levels and write the label inside each node, not on the edges. 3. Scan for repeats. Circle a repeated pair and say out loud that their subtrees are identical. 4. Ask what else the result depends on that is not in the label — and if something is, either add it to the label or admit the nodes are not duplicates. 5. Say whether the distinct-label count looks small relative to the node count. That is the finding. A candidate who does steps 1 through 3 is competent. A candidate who volunteers step 4 unprompted is the one who has debugged a search that returned different answers on different runs. ## Common traps - **Labelling by path instead of by state.** Then no two nodes ever look equal and the redundancy is invisible. - **Assuming visual similarity means duplication.** Two subtrees of the same shape are not the same computation unless their labels match. - **Forgetting the depth argument.** The same position with different remaining depth is a different label and a different subtree. - **Ignoring in-place mutation.** A recursion that edits shared state makes the tree unreliable as a model of what actually ran. - **Declaring a win from one circled pair.** Redundancy has to be widespread to be worth exploiting.

Why must the remaining depth be part of the label and not just the position?
Because the invocation's result depends on both. The same position explored with three plies left and with one ply left expands into different subtrees and returns different answers. Treating those two nodes as duplicates would let a shallow result stand in for a deep one, which is a correctness bug, not an optimisation. The label has to be the full argument tuple.
A search returns different answers on different runs even though the input is fixed. What does that suggest about the tree you drew?
That the invocations depend on something outside their labels — most often a board or accumulator mutated in place and not fully restored, so a node's result depends on which siblings ran first. The drawn tree then models a computation that did not happen. Fix the hidden dependency, or fold it into the label, before drawing any conclusion about duplicated subtrees.
How would you sanity-check that duplication is widespread rather than incidental?
Instrument the exploration to record each label it visits and compare the count of visits with the count of distinct labels at a small depth you can afford to run. A large gap means convergence is systemic and worth exploiting; a small gap means the tree really is as wide as it looks and effort belongs in pruning or the depth cap instead.

saying these in an interview costs you the question

Labels nodes by move sequence rather than by state
Calls same-shaped subtrees duplicates without comparing labels
Leaves the remaining depth out of the label
Ignores mutable state the recursion edits in place
Declares heavy redundancy from a single circled pair

In a drawn game-search tree, how do you tell that different move orders re-explore the same position?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The reading that matters

Two trees that look the same and are not

Why this is a senior reading and not a junior one

Doing it at the whiteboard

Common traps

▾common follow-ups3 questions

▾red flags5 flags

§ context

▾related questions5 questions

▾related topics3 topics

The reading that matters

Two trees that look the same and are not

Why this is a senior reading and not a junior one

Doing it at the whiteboard

Common traps

answer

go deeper

context