skip to content

When path copying replaces one leaf of an immutable tree, exactly which nodes must be freshly allocated?

level: middleimportance: must knowfreq 54%

answer

  1. one route, bottom to top
  2. a stale child reference forces a rebuild
  3. depth-many nodes, plus the new value
  4. one slot per rebuilt node differs
  5. references copied, subtrees reused

basics

~20 s

The replacement leaf, plus a new copy of every node on the route from the root down to it, including a new root. That is depth-many nodes. Every node off the route is reused as-is.

solid answer

~40 s

Exactly the nodes on one root-to-leaf route, from the bottom up. You build the new leaf first. Its parent held a reference to the old leaf, so the parent cannot stay as it is — you build a new parent identical to the old one except in that one slot. That new parent now makes *its* parent stale for the same reason, and the argument repeats all the way to a new root, which is the handle to the new version. So the count is the route's length: depth-many nodes, one per level. In each rebuilt node, the slots other than the changed one are filled with the *same child references* the old node held — references are copied, subtrees are not.

code

pseudocode · 11 lines
pseudocode
function setAt(node, route, i, value):
    if i == length(route):
        return value                       // the replacement leaf

    slot        = route[i]
    newChild    = setAt(node.children[slot], route, i + 1, value)
    newChildren = copyOf(node.children)    // copies b references only
    newChildren[slot] = newChild
    return Node(newChildren)               // one new node for this level

newRoot = setAt(oldRoot, route, 0, value)  // oldRoot is untouched

go deeper

for a junior

Remember the two halves: everything on the route from root to the change is new, everything off it is reused. The root is always new.

for a middle

Derive it rather than reciting it — a node holding a changed child reference must be reissued — and give the count as depth-many nodes plus the replacement value.

for a senior

Be able to read an update routine and say which line does the sharing; the tell is a shallow copy of one node's slot array next to a recursive call on a single slot.

for a principal

Judge where the depth-shaped cost stops paying: very shallow structures, write-everything workloads, or readers that need one contiguous block rather than a node chain.

The question is really "how far up does the damage go, and how far sideways does it not go?" The answer is: all the way up, and not at all sideways. ## The rule, derived rather than memorised A node in an immutable structure is a fixed bundle of child references. Take the hourly snapshot of a directory tree again and change one file: 1. The file's contents differ, so the **leaf** cannot be the old leaf. Build a new one. 2. The directory that contained it held a reference to the *old* leaf. Its contents must differ too, so build a **new directory node**, identical to the old one except that one slot now names the new leaf. 3. That directory's parent held a reference to the *old* directory node, so it is stale by exactly the same argument. Build a new one. 4. Repeat until you build a **new root**. The new root is the new version; there is nothing above it to invalidate. The recursion terminates at the root, and the set of nodes it built is precisely the route. Everything else in the tree was never examined, never compared, and never copied. ## Counting it If the route from the root to the changed value passes through the root, three interior nodes and the leaf, the update allocates **five** nodes. In general, for a tree of depth `d`, a single-position update allocates `d + 1` nodes: one per level plus the replacement value itself. Within each rebuilt node, `b` child references are copied for a branching factor of `b`, of which exactly one differs. | What | How many | Copied or built | |---|---|---| | Nodes on the route | one per level, plus the new leaf | built | | Child references inside a rebuilt node | the node's width | copied as references | | Subtrees off the route | all the rest | neither — the same node is reused | | Nodes written in place | zero | nothing is ever written | ## Why you cannot stop early The tempting shortcut is to build the new leaf and then just point the existing parent at it. That is a write into a node the old root still reaches, and the old version would silently acquire the new file. Once any ancestor is written in place, every version that shares it changes, and "the version I published an hour ago" stops meaning anything. So the update walks up to the root, and the decision at each level is mechanical: *this node holds a reference that changed, therefore this node is reissued.* The mirror shortcut — rebuilding the siblings too — is the other failure, and it is the expensive one: siblings hold no changed reference, so rebuilding them buys nothing and costs the size of the structure. ## The shape in code A path-copying update is naturally recursive, descending along the route and rebuilding on the way back out. The descent chooses one slot per level; the return builds one node per level. Two properties make it correct: - **Only one slot per rebuilt node differs.** Everything else in the node is the old reference, verbatim. - **The function returns the new node** rather than modifying its argument. The caller — the level above — is the one that needs it, and it needs it precisely because it must rebuild itself. ## Consequences worth stating - **Cost is depth, not size.** Both the allocation count and the pointer-chasing are proportional to the route length. - **The old root remains a complete, correct handle** to the previous version, because no node it reaches was touched. - **Two updates to nearby positions share almost everything**, since their routes overlap near the root and diverge low down; the second update's route passes through nodes the first update created. - **Nothing is compared.** The update does not check whether the new value equals the old one; unless the implementation deliberately short-circuits an identical write, replacing a value with an equal value still rebuilds the route. Stated as one sentence: *rebuild bottom-up along one route, copy references not subtrees, return a new root.*

  • Why can't the update stop at the parent of the changed leaf?
    Because that parent now holds a different child reference, so it is a different node. Leaving it in place would mean writing into a node the old root still reaches, and the previous version would change underneath whoever holds it.
  • What do the untouched slots of a rebuilt node contain?
    The very same child references the old node held. They are copied as references — a fixed, small amount of work per node — and the subtrees they name are never visited, compared or duplicated.
  • Two separate updates change two leaves under the same parent. What do the two results share?
    Every subtree off both routes, and nothing on the shared upper route: the second update copies the upper nodes again, so those levels now exist in three versions. The deep, untouched subtrees are still one set of nodes.

saying these in an interview costs you the question

  • Says only the changed leaf and its immediate parent are new
  • Rebuilds the sibling subtrees while walking past them
  • Thinks the update mutates the parent's slot to point at the new child
  • Cannot say that the root is always among the new nodes
  • Counts the copied child references as copied subtrees