skip to content

Why can two versions of a structurally shared tree be compared without walking every node?

level: middleimportance: nice to knowfreq 28%

answer

  1. sharing leaves a trail
  2. same node, unchanged subtree
  3. prune where identity matches
  4. the proof runs one way only
  5. cost tracks the change, not the tree

basics

~10 s

Wherever both versions hold the same node, everything below it is unchanged by construction, so the walk stops there. Only rebuilt routes differ, so the comparison costs the size of the change.

solid answer

~40 s

Because sharing turns node identity into a proof of sameness. Nothing is ever written in place, so if the two versions hold *the same node* at a position, that node's contents — and everything reachable from it — are identical in both, and the traversal can prune the whole subtree without looking inside. What is left to walk is exactly the routes that were rebuilt, so the comparison costs the size of the change rather than the size of the tree. The test is one-sided, though: the same node proves unchanged, but a different node proves only that it was reissued. Two distinct nodes may still hold equal contents, so a cheap comparison of this kind can report a difference where a value comparison would find none.

code

pseudocode · 8 lines
pseudocode
function diff(a, b, out):
    if a is b:                       // same node: subtree unchanged
        return
    if isLeaf(a) or isLeaf(b):
        out.append(a, b)
        return
    for slot in 0 .. width - 1:      // both nodes have the same width
        diff(a.children[slot], b.children[slot], out)

go deeper

for a junior

Take away one fact: if both versions point at the same node, nothing below it changed, so the comparison can skip it entirely.

for a middle

State the implication in the right direction — same node proves unchanged, different node proves only rebuilt — and name the write-once rule that licenses it.

for a senior

Use it to scope downstream work after a version changes, and say how you would keep an over-reported difference from turning into wasted recomputation.

for a principal

Weigh whether the system can tolerate a cheap one-sided comparison, or must pay for exactness on the rebuilt routes, and set that expectation for consumers.

This is the payoff that people who have only heard "immutable updates are cheap" tend to miss: sharing does not just make writing cheap, it makes **comparing two versions** cheap. ## The property being exploited In a structurally shared design, two facts hold together: - No existing node is ever written. Every change allocates. - An update reissues exactly the nodes on the route it changed. Put those together and you get a strong implication: **if both versions hold the same node at a position, no update between them touched anything below that position.** The subtree is not "probably equal" or "equal at the time we checked" — it is the same allocation, and it cannot have changed. ## How the comparison uses it Walk the two versions together from their roots. At each position: 1. If both sides hold **the same node**, stop — the entire subtree is unchanged, however large it is. 2. Otherwise, the node was reissued somewhere below, so descend into it and repeat. 3. At the leaves, report the differing values. In the hourly-snapshot frame: to list what changed between two consecutive versions of a directory tree, you never open a directory that both versions name with the same node. The walk follows only the routes that were rebuilt, so its cost is proportional to what changed plus the depth, not to how much data the snapshot holds. ## Which direction the proof runs This is where the mechanism is easy to state backwards, so be exact: | Observation | What it proves | |---|---| | Both versions hold the same node | The subtree is unchanged — certain | | The versions hold different nodes | The node was rebuilt — the contents may still be equal | The test is **one-sided**. It is sound for *skipping* and unsound for *concluding a difference*. Two nodes can differ in identity yet hold equal contents when: - a position was overwritten with a value equal to the one already there, which still rebuilds the route; - two subtrees were built separately and happen to hold the same elements — sharing arises from reuse during an update, never from a search for equal content; - a version was rebuilt wholesale from an external source rather than derived by updating the previous one. So a diff built on identity may over-report. If exact results are required, fall back to a value comparison **only** on the subtrees whose identities differ — which is still far less work than walking everything. ## Why this matters beyond diffing The same prune underlies a family of practical behaviours: - **Deciding what to re-render, re-index or re-publish** after a version changes: the work list is the set of positions whose node identity changed. - **Fast equality for whole versions**: comparing two roots by identity answers "identical version" immediately when the answer is yes, and costs nothing when it is no. - **Cheap change notification**: a consumer that remembers the node it last processed can detect at a glance whether its region moved. ## The failure to avoid All of this rests on the write-once discipline. If any node reachable from two versions can be written in place, identity stops proving anything: the same node could have different contents than it had when the older version was published, and the prune would skip a subtree that really did change. The cheap comparison is not a free-standing trick — it is a consequence of the same rule that makes sharing legal in the first place. Said in one sentence: *because nothing is ever written, sameness of node is proof of sameness of subtree — and that one-sided proof is what lets a comparison skip everything the change never reached.*

  • Does a differing node reference prove that the contents differ?
    No. It proves only that the node was reissued. Writing a value equal to the one already there still rebuilds the route, and two equal subtrees built independently are different nodes, so an identity-based comparison can over-report.
  • What makes the prune sound in the first place?
    The write-once rule. Because no existing node is ever modified, a node reachable from two versions holds the same contents in both, and so does everything below it. If in-place writes were possible, identity would prove nothing.
  • How would you get an exact difference without losing the speed-up?
    Prune on identity, then fall back to a value comparison only on the subtrees whose identities differ. You keep the skip over everything the change never reached and pay full comparison cost only on the rebuilt routes.

saying these in an interview costs you the question

  • Says different node references prove the contents differ
  • Expects independently built equal subtrees to be the same node
  • Thinks the comparison must walk every element to be correct
  • Believes identity pruning still works when nodes can be written in place
  • Assumes a rewrite with an equal value leaves the route untouched