An immutable tree-shaped value gets one leaf replaced — why is the new version not a full copy?
answer
- the change has a route
- rebuild the route, reuse the rest
- siblings carried over by reference
- same node, not an equal copy
- one path deep, not one tree wide
basics
~20 sOnly the nodes along the route from the root to the changed leaf are rebuilt; every subtree the change never touched is pointed at by both versions. The copy is one path deep, not one tree wide.
solid answer
~40 sBecause the update rebuilds a route, not a structure. Replacing one leaf produces a new leaf, a fresh copy of every node on the route from the root down to it, and a new root. Everything hanging off that route — the siblings at each level — is carried into the new version *by reference*, so both versions literally point at the same nodes. Nothing is written in place, and that is what makes the sharing safe: a node both versions can reach can never change under either of them. Work and extra memory therefore scale with the depth of the tree rather than with the number of elements in it, which is what makes an immutable update affordable at all.
code
pseudocode · 7 linesoldRoot = Node(children = [a, b, c, d])
newC = Node(children = replaceSlot(c.children, 2, newLeaf))
newRoot = Node(children = [a, b, newC, d])
// a, b and d are the SAME nodes both roots point at.
// Only newC, newLeaf and newRoot were allocated.go deeper
Be able to draw it: the changed leaf, the chain of nodes above it redrawn, and arrows from the new nodes into the old untouched subtrees. Say "same node", not "same value".
Explain why every ancestor has to be rebuilt — each one holds a child reference that changed — and put a cost on it: work proportional to depth, not to element count.
Show you can tell real sharing from a deep copy in a running system, by comparing an untouched subtree across two versions by reference rather than by value.
Frame it as the bet the design makes: cheap versions and lock-free reads bought with per-update allocation and an extra indirection on every read. Say when that bet is wrong.
**Structural sharing** is the mechanism that makes immutable updates affordable. A new version of a value reuses — by reference, not by copying — every part of the old version that the update did not touch, and rebuilds only the nodes the update's route actually passes through. ## The objection, stated fairly The objection is the reason this subject is asked at all: *if a value can never change, then producing a changed value must copy the whole thing, and that is ruinous.* It is right about one thing. You genuinely cannot write into the old value, because someone else may still be looking at it. It is wrong about what follows. "Cannot write into it" does not imply "must duplicate it" — it only implies that whatever the new version does not reuse, it must build. ## Work the update actually does Take the frame of an hourly snapshot of a directory tree: every hour you publish a new version of the tree, and one file inside one deep directory has changed. Path copying builds: - a **new leaf** holding the changed file's contents; - a **new node for each directory on the route** from the root down to that file, each one identical to its old counterpart except in the single slot that names the changed child; - a **new root**, which is the handle to the new version; - **nothing else at all** — every directory hanging off the side of that route is put into the new parent as the very same node the old parent held. | Node | In the old version | In the new version | What was built | |---|---|---|---| | The changed file | old contents | new contents | a new node | | Each directory on the route | old child slot | one slot swapped | a new node per level | | The root | old root | new root | a new node | | Every sibling directory | present | the identical node | nothing | The phrase to be precise about is "the identical node". The new parent does not hold a copy of the sibling that happens to be equal to it. It holds the same node — the same allocation, reachable from both roots. ## Why the cost is a path and not a tree The number of nodes rebuilt is the **length of one root-to-leaf route**, which is the tree's depth. For a tree with `n` leaves and a branching factor of `b`, that depth is about log-base-b of `n`. With a wide branching factor and a million leaves, that is a handful of levels — so a single-element update rebuilds a handful of nodes and copies a few hundred child references, against the millions of elements an eager whole-copy would touch. The extra memory the new version needs follows the same shape: it is proportional to the route's length times the width of a node, not to the size of the tree. It is not free — the new nodes are real allocations — but it does not grow as the data grows in the way a full copy does. ## What sharing requires to be sound Sharing is legal only because the shared nodes are **write-once**. Two versions may point at one node precisely because no operation will ever reach in and change it; every operation allocates instead. The moment one node reachable from two versions can be written in place, a write made "in the present" becomes visible in a version that was published in the past, and the whole scheme fails. That is why this mechanism belongs to immutable data and not to ordinary mutable structures that happen to be linked. ## What it does not buy you - It does **not** make the update free. There is real allocation on every level of the route. - It does **not** deduplicate equal-but-separately-built subtrees. Sharing arises from *reuse* during an update, not from a scan for equal content. - It does **not** help a change that touches every leaf. Rewriting every element rebuilds every route, and the routes together cover the tree. - It does **not** apply only to trees in name. Any structure whose elements are reached through a chain of nodes — wide-branching tries included — can be updated this way; a flat array of `n` slots cannot, because there is no route to copy, only the whole block. The short form to say out loud in an interview: *an immutable update copies a path, shares everything off the path, and writes nothing.*
- If the changed leaf is a direct child of the root, how many nodes does the update allocate?Two: the replacement leaf and a new root whose slot for it points at the replacement. The root's other children are carried over as the same nodes, so nothing below them is built or examined.
- Which existing nodes does such an update write to?None. Path copying only allocates. That is the whole trick: because no existing node is ever written, a node reached from two versions has the same contents in both, which is what makes carrying siblings over by reference safe.
A new edition of a reference work reprints the one chapter that changed and binds the untouched chapters from the existing print run. Both editions are complete, and most of the paper is the same paper.
saying these in an interview costs you the question
- Says an immutable update must deep-copy the whole structure
- Thinks the shared subtrees are copies that merely happen to be equal
- Believes only the changed leaf is new and its ancestors stay as they are
- Believes the parent's child slot can just be written in place
- Claims the new version costs no extra memory at all
- Assumes sharing still works when a shared node can be mutated