Virtual DOM III: Diff and Patch

The problem

Given the old and new virtual trees (the { type, props, children } objects from part one), update the real DOM to match the new tree — touching as little of the DOM as possible.

This is the payoff of the trilogy: serialize gave us UI-as-data, deserialize gave us render, and diffing is what makes the whole detour worth it — re-rendering by rebuilding everything works, but it destroys focus, selection, scroll positions, and video playback state along with the nodes. Reconciliation exists to preserve the DOM nodes that didn't change.

The general tree-edit-distance problem is O(n³). React's insight — and what you're implementing — is a set of heuristics that get to O(n): different type → replace the subtree; same type → patch in place and recurse; children → compare positionally (keys upgrade this — see below).

Implementation

render here is part two's deserialize.

function changed(a, b) {
  if (a.type !== b.type) return true;                 // div → span: replace
  if (a.type === "text") {
    return a.props.nodeValue !== b.props.nodeValue;   // text: compare content
  }
  return false;                                       // same type: patch in place
}
 
function patchProps(el, oldProps, newProps) {
  for (const name of Object.keys(oldProps)) {
    if (!(name in newProps)) el.removeAttribute(name); // removed props
  }
  for (const [name, value] of Object.entries(newProps)) {
    if (oldProps[name] !== value) el.setAttribute(name, value); // added/changed
  }
}
 
function patch(parent, oldVNode, newVNode, index = 0) {
  const el = parent.childNodes[index];
 
  if (oldVNode === undefined) {                 // node added
    parent.appendChild(render(newVNode));
    return;
  }
  if (newVNode === undefined) {                 // node removed
    parent.removeChild(el);
    return;
  }
  if (changed(oldVNode, newVNode)) {            // replace the whole subtree
    parent.replaceChild(render(newVNode), el);
    return;
  }
 
  if (newVNode.type !== "text") {               // same element: patch & recurse
    patchProps(el, oldVNode.props, newVNode.props);
    patchChildren(el, oldVNode.children, newVNode.children);
  }
}
 
function patchChildren(el, oldChildren, newChildren) {
  const common = Math.min(oldChildren.length, newChildren.length);
 
  // 1. patch the overlap, position by position
  for (let i = 0; i < common; i++) {
    patch(el, oldChildren[i], newChildren[i], i);
  }
  // 2. append new extras
  for (let i = common; i < newChildren.length; i++) {
    el.appendChild(render(newChildren[i]));
  }
  // 3. remove old extras — BACKWARDS, so indices don't shift under us
  for (let i = oldChildren.length - 1; i >= common; i--) {
    el.removeChild(el.childNodes[i]);
  }
}

Dry run

// tiny helpers for building vnodes by hand:
const h = (type, props = {}, children = []) => ({ type, props, children });
const text = (nodeValue) => ({ type: "text", props: { nodeValue }, children: [] });
 
const oldV = h("ul", {}, [
  h("li", { class: "item" }, [text("Alpha")]),
  h("li", {}, [text("Beta")]),
]);
const newV = h("ul", { class: "list" }, [
  h("li", { class: "item done" }, [text("Alpha")]),
  h("li", {}, [text("Bravo")]),
  h("li", {}, [text("Charlie")]),
]);
 
patch(container, oldV, newV);
// ul:        same type → patchProps sets class="list"       (1 attribute write)
// li[0]:     same type → class "item" → "item done"          (1 attribute write)
//   text:    "Alpha" === "Alpha" → NOTHING happens           (0 writes)
// li[1]:     same type, props equal → recurse
//   text:    "Beta" → "Bravo" → replace text node            (1 node swap)
// li[2]:     old undefined → append rendered <li>Charlie</li> (1 append)
// TOTAL: 4 DOM mutations. Rebuild-everything: ~9 node creations + teardown.

The zero-write line for unchanged text is the whole sales pitch — and the <li>Alpha</li> element object identity is preserved: if it held focus or selection, it still does.

The details that separate answers

• Backwards removal in patchChildren. Removing childNodes[i] shifts every later index down; a forward loop removes the wrong nodes (delete index 2, old index 3 becomes 2, loop moves to 3 — one survives). Iterating removals from the end is the classic index-invalidation fix, and it's the planted bug in this question.
• Replace-don't-diff across types. A div → span change could theoretically keep children; the heuristic says subtrees of different types are different things — cheap, and right in practice. This single assumption is what collapses O(n³) to O(n); name it as the trade.
• patchProps diffs three ways — removed, added, changed. Forgetting the removal pass leaves stale attributes (class from a previous state lingering) — the second most-planted bug.
• Text nodes are compared by value, not replaced wholesale — and note changed treats two text nodes with equal content as unchanged, which is the common case in any list re-render.

Why keys exist — the positional-diff failure

Positional comparison is O(n) but identity-blind. Prepend one item to a 500-row list:

old: [A, B, C]        new: [X, A, B, C]
positional diff: patch A→X, B→A, C→B, append C   → rewrites EVERY row
keyed diff:      insert X at 0                    → one insertion

Worse than performance: because element objects are reused positionally, row state that lives in the DOM (focus, input values not mirrored to data, CSS transitions) attaches to the wrong logical item after the shift. That's precisely the bug class React's key warning prevents — keys let the differ match children by identity (build an old-key → element map, reorder/insert/remove instead of rewrite), turning the child diff into the move-minimizing algorithm every real framework ships (React's two-pass approach, Vue's double-ended diff, longest-increasing-subsequence tricks in Inferno/Vue 3). Implementing keyed diff is the natural 20-minute extension; explaining the focus-attached-to-wrong-row bug is the part interviewers actually require.

Edge cases interviewers probe

• The forward-removal index bug — see above; expect to trace it.
• Attributes vs properties — patchProps writes attributes; live form state (value, checked) needs property writes and doesn't round-trip through attributes — part two's layer distinction returns with interest. Real frameworks maintain a per-prop policy table.
• Event handlers — not diffable from serialized trees at all (part one explains why); frameworks keep handlers in the vnode and patch listeners separately — or sidestep via delegation, which is historically exactly what React did.
• Reordering without keys — correct output, pathological mutation count + state-migration bugs; the keys section.
• replaceChild on the root — if the root types differ, parent is the container; the index = 0 default handles it, but only if the container holds exactly the tree — mounting discipline from part two matters here.

Common mistakes

• Forward-loop removals (index shift).
• No removed-props pass (stale attributes accumulate).
• Diffing children by rebuilding them all when lengths differ — the three-phase overlap/append/remove structure is the point.
• Comparing whole subtrees with deep-equal "to skip work" — an O(n) comparison to maybe save an O(1) write inverts the economics; the differ IS the comparison.
• Presenting the VDOM as free — diffing costs CPU and two trees of memory; frameworks like Svelte 5/Solid compile change paths instead (the part-one closing argument); knowing both sides is 2026 literacy.

Follow-up questions

• "Implement keyed child diffing." — old-key map → reuse/move nodes (insertBefore), remove leftovers; discuss why index-as-key defeats the entire mechanism (it is positional diff with extra steps) — the code-review-famous anti-pattern, explained from first principles.
• "Emit patches as data instead of applying directly." — { op, path, ... } lists enable batching, undo, and cross-boundary shipping (worker-side diff, main-thread apply) — the Immer-patches idea meeting the DOM.
• "Where do component functions fit?" — when type is a function, call it with props to get the subtree, compare the results — and memoize the call when props are shallow-equal: you've just derived React.memo from memoizeLast.
• "How does batching interact?" — collect state changes, diff once per frame (rAF scheduling); explains why frameworks batch setState and why layout reads between writes force sync reflow (event-loop rendering slot).
• "What did React Fiber change about this?" — the diff became interruptible: linked-list traversal instead of recursion so work can pause/resume across frames — the recursion-to-explicit-stack conversion deployed for schedulability, not stack depth. One sentence that lands very well at senior loops.