The diffing algorithm: heuristics and keys

The first lesson established the loop — new tree, old tree, diff, apply the difference — and the second lesson established exactly what's in those trees: nested { type, props, key, ref } element objects. This lesson answers the question both left open: how does React actually compare two trees cheaply? The honest computer-science answer is that it can't, not in general — so it doesn't try. It makes two simplifying bets instead, and those two bets are the entire diffing algorithm.

The naive problem: general tree diffing is too slow to run per render

Computing the minimal set of edits to turn one arbitrary tree into another is a well-studied problem, and the optimal algorithms for it run in roughly O(n³) time in the number of nodes. That is a cost you could maybe tolerate once, offline. React needs to do something like this on every state change, potentially many times a second, on a tree that can have thousands of nodes. O(n³) at that frequency would make React unusable — a few thousand nodes would mean billions of comparison operations per render.

So React does not implement a general tree diff. It implements a heuristic diff — one that gives up on being provably optimal in every case, in exchange for being reliably fast in the cases that actually occur in UI code. The trade is: assume real UIs have some structure, and use that structure to skip almost all of the comparison work a fully general algorithm would do.

Heuristic one: different type at a position means tear down and rebuild

The first assumption: two elements of different types produce fundamentally different trees. If, at the same position in the tree, the previous render had a div and the new render has a span — or the previous render had <UserProfile /> and the new render has <LoginForm /> — React does not try to figure out which parts of the old subtree could be salvaged. It doesn't diff into it at all. It tears the whole thing down: destroys the old DOM nodes and unmounts the old component instances (running their cleanup), then builds the new subtree from scratch as if nothing had been there before.

// Render 1
<div className="card">Ada</div>

// Render 2 — SAME type ('div') at this position
<div className="card highlighted">Ada</div>
// React KEEPS the existing DOM node, patches className only.

// Render 3 — DIFFERENT type ('div' -> 'section') at this position
<section className="card highlighted">Ada</section>
// React DESTROYS the div and everything in it, builds a new <section> from scratch.

The same rule applies to components, and it's the part that surprises people: swapping type from ComponentA to ComponentB at the same position throws away ComponentA's entire subtree and all of its state, even if both components happen to render visually identical output. React never looks inside to check "would this actually be compatible?" — different type is, by fiat, treated as "assume incompatible," full stop. That's the bet: real code rarely swaps a div for a section at the same spot and expects continuity, so it's safe to skip checking.

Heuristic two: same type at a position means update in place and recurse

The second assumption is the mirror image: if the type at a position is the same as last time, the underlying node is assumed to still be compatible, so React keeps the existing DOM node (or component instance) exactly as it is, only patching the props/attributes that actually changed — and then recurses into the children, running this same two-heuristic process one level down. It does not rebuild; it mutates minimally and continues.

This is what makes the loop from the first lesson cheap in the common case: most of a typical re-render is "same type here, same type here, same type here" all the way down, and each of those checks is O(1) — compare a type, compare a handful of props — not a search over possible matches. That is where the linear time comes from: one bounded-cost decision per position, not a combinatorial search across the whole tree.

Diffing children: by default, React matches by position

Recursing "into the children" raises an immediate question: when a node has a list of children, how does React decide which old child corresponds to which new child? The default answer is unglamorous: by index. The element that was first in the old children array is compared against whatever is first in the new children array, second against second, and so on — position, not identity.

For a list that only ever changes in place — the same items, same order, just some text or a class updating — index matching works fine, because position and identity happen to coincide. But it breaks down the moment items are inserted, removed, or reordered. Prepending a single new item to the front of a list means everything that used to be at index 0 is now at index 1, everything at index 1 is now at index 2, and so on — so at every single position, React's heuristic-one check ("did the type/identity here change?") sees what looks like a changed item, because index-based comparison has no way to know "the old item 0 just moved to slot 1; it didn't change." Depending on what's in the row, this can mean React updates every row's DOM unnecessarily — or worse, if rows hold internal state, uncontrolled inputs, or per-item component state, that state can get attached to the wrong logical item, because as far as index-based matching is concerned, "index 3" is still "index 3," even though a different piece of data now lives there.

Keys: telling React what actually moved

This is exactly the gap key closes — the reserved element field from the previous lesson. A stable, unique-per-sibling key tells React "match children by this identity, not by position." With keys present, React can look at the new children list, find the old child that shares each key, and correctly recognize moves — this item didn't change, it just relocated from index 0 to index 1 — rather than seeing a changed item at every shifted position. That lets React preserve exactly the DOM nodes and component state that should be preserved, and apply exactly one insert (or removal, or reorder) instead of a cascade of "different" updates down the whole list.

// No stable keys — index used implicitly as the key
{items.map((item, i) => <Row key={i} data={item} />)}
// Insert a new item at the front: every row's index shifts by one.
// React sees "index 0's content changed, index 1's content changed, ..."
// for the WHOLE list — even though nothing about most rows actually changed.
// If Row holds its own state (e.g. an <input> the user was typing into),
// that state can end up attached to the wrong row's data after the shift.

// Stable keys — identity, not position
{items.map((item) => <Row key={item.id} data={item} />)}
// Insert a new item at the front: React matches every existing row by its
// stable id, sees they're unchanged, and performs exactly one DOM insert
// for the new row. Every other row's DOM node and state stay untouched.

See it happen

The clearest way to see why index keys and stable keys produce different DOM operations for the same list change is to watch React's own work log. The playground below runs the same insert/remove/reorder against a list keyed by index and the same list keyed by stable id, and shows exactly which DOM nodes get touched, replaced, or left alone in each case.

The two assumptions, restated as the bet React makes

Strip away the mechanics and the whole algorithm is two bets about how real UI trees tend to change:

1. A type change at a position means the whole subtree is different — don't bother diffing into it, tear down and rebuild. This is almost always true in practice: components rarely masquerade as unrelated components at the same slot.
2. Same type at a position means the node is still the right one to update in place — patch props, recurse into children, matching by index unless told otherwise. This is also almost always true — until a list's order changes, which is precisely the case key exists to handle.

Neither bet is provably correct in every conceivable case — that's what makes it a heuristic rather than an exact algorithm. What it buys is the thing the first lesson already told you to expect: not the theoretical optimum, but a reliably linear, "good enough," automatic cost for the overwhelming majority of real re-renders.

Where this goes next

Diffing decides what changed. It doesn't, by itself, explain how React can pause that work partway through a giant tree and come back to it later without losing its place, or how state survives across all of this even though a brand-new element tree is produced every render. Fiber is the data structure that makes that possible — the actual structure this diffing process walks over, unit by interruptible unit.