cf.completefrontend
ALGORITHMS IN FRONTEND WORK · ADVANCED

Virtual DOM diffing

Compare the old and new trees of elements node by node and list the smallest set of changes to apply to the real page.

Time O(n + p)Space O(depth)3 practice problemsStep-through picture

The idea

Frameworks like React let you describe what the page should look like as a tree of plain objects, often called a virtual DOM. Each object has a type like "div", some props like { class: "card" }, and children. When data changes, you describe the new tree. The framework must then change the real page to match, touching as little as possible, because real DOM changes are slow.

Finding the truly smallest set of changes between two trees is expensive: the best known general methods take about O(n^3) time, too slow for thousands of elements. React instead uses two simple rules. If two elements have a different type, replace the whole subtree without looking inside. If they have the same type, keep the element, update the props that changed, and compare the children. Children are matched by key when you give one, otherwise by position.

With those rules, each node is compared once, so diffing is O(n). The rules can miss a cheaper update in rare cases, but in real apps they work very well.

An everyday example

Updating a printed seating chart

You have last week's seating chart on the wall and this week's version on paper. You compare them table by table. If a table changed from a round table to a long one, you throw away the old table and everything on it and set up the new one. If it is the same kind of table, you only swap the name cards that changed, then check each seat. Seats that only exist in the new chart get added; seats that disappeared get removed.

How the example maps to the code
In the exampleIn the code
A table on the old and new chartoldNode and newNode
A different kind of tableoldNode.type !== newNode.type, giving a replace patch
Swapping the name cards that changedprop patches for keys whose values differ
A seat only in the new chart!oldNode, giving an insert patch
A seat that disappeared!newNode, giving a remove patch

From the slow way to virtual dom diffing

  1. Start with the obvious way to update the page: throw away the old elements and build all the new ones, as setting innerHTML does. It is correct, but it is slow for big pages, and it destroys things the user can see. Focus jumps out of the input, the cursor position is lost, and scroll positions and playing videos reset.
  2. So we want to keep every real element we can and change only what differs. The exact answer, the smallest list of edits that turns one tree into another, is called tree edit distance. General methods for it take about O(n^3) time. For 1,000 elements that is around a billion steps, on every update.
  3. Look at how UIs really change. An element almost never jumps to a different parent. And when an element changes type, like a ul becoming an ol, or a form becoming a loading spinner, its inside is almost always different too. So compare only nodes that sit at the same place, and give up early when the type differs.
  4. That leaves two rules. Different type: replace the whole subtree and don't look inside. Same type: keep the element, patch only the props that changed, and then compare the children pair by pair. Each node is looked at once, so the cost is linear. That recursion is virtual DOM diffing.

How it works

  1. Call diff(oldNode, newNode, "0", patches) on the two roots. path names a node by the child positions from the root, like 0.1.
  2. If there is no old node, the new one was added: push an insert patch.
  3. If there is no new node, the old one was deleted: push a remove patch.
  4. If the type differs, push a replace patch and stop. Nothing inside is compared.
  5. Otherwise the element is kept. For every prop name in either node, push a prop patch if the value changed (null means removed).
  6. Then diff the children in pairs by position, up to the longer list's length, with paths path.0, path.1, and so on.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function diff(oldNode, newNode, path = "0", patches = []) {
  2. if (!oldNode) {
  3. patches.push(["insert", path, newNode.type]);
  4. } else if (!newNode) {
  5. patches.push(["remove", path]);
  6. } else if (oldNode.type !== newNode.type) {
  7. patches.push(["replace", path, newNode.type]);
  8. } else {
  9. const keys = new Set([...Object.keys(oldNode.props), ...Object.keys(newNode.props)]);
  10. for (const key of keys) {
  11. if (oldNode.props[key] !== newNode.props[key]) {
  12. patches.push(["prop", path, key, newNode.props[key] ?? null]);
  13. }
  14. }
  15. const count = Math.max(oldNode.children.length, newNode.children.length);
  16. for (let i = 0; i < count; i++) {
  17. diff(oldNode.children[i], newNode.children[i], `${path}.${i}`, patches);
  18. }
  19. }
  20. return patches;
  21. }

How fast it is

TimeO(n + p)
Extra memoryO(depth)

Every node is compared once and every prop is checked once. The recursion keeps one call per level of the tree.

  • Best caseO(1)

    The two roots have different types. One replace patch is pushed and nothing inside is compared. Building the new subtree later still costs time.

  • Average caseO(n + p)

    A typical update: most nodes keep their type, so every node and every prop is compared once.

  • Worst caseO(n + p)

    Every node keeps its type, so all n positions and all p props are compared. It never gets worse than linear.

Common mistakes

  • Comparing children inside nodes of different types. The rule is to replace; looking inside wastes time and keeps state that should be reset.
  • Only looping over the new node's props. Props that were removed are then never cleared. Loop over the keys of both.
  • Using array indexes as key in lists that get reordered or filtered. The keys then follow positions, not items, and state ends up on the wrong row.
  • Comparing props that are objects or functions with !==. A new inline object is a different object each render, so it always looks changed; that is why React uses memo and useCallback.

When to use it

Look for these clues in a problem:

  • You are given two versions of a tree, such as UI nodes, and must list the changes between them.
  • The question describes rules like "same type means update, different type means replace".
  • Children are matched by position or by a key field.
  • The answer is a list of patch operations, often with paths like 0.1.2.

Check yourself

Answer each one in your head first, then open it.

The old root is a div with 500 nodes inside and the new root is a main. How many patches does diff push?

One: ["replace", "0", "main"]. Different types stop the comparison right away, so nothing inside is looked at.

Why does the code loop over the prop names of both nodes, not just the new one?

A prop that was removed only appears in the old props. Looping over the new props alone would never find it, so the old value would stay on the page.

Why does changing a component's type reset its state?

Different types mean replace: the old subtree, including any state in it, is destroyed and a new one is built. Nothing inside is matched up.

What does diff return when the old and new trees are equal?

An empty list. Every node has the same type and no prop value differs, so no patch is pushed.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The promise is about correctness, not about being the smallest: after diff(oldNode, newNode, path) returns, applying the patches it pushed turns the old subtree at path into one that matches newNode. For the first three cases this is clear: an insert adds the new subtree, a remove deletes the old one, and a replace swaps one for the other.

For the same-type case, it holds by working up from the leaves. Every prop name in either node is checked, so after the prop patches the props match, including removed ones, which are sent as null. Each child position up to the longer list is handled by a smaller call to diff, which keeps the same promise for that child. So the element, its props, and every child end up matching.

The recursion ends because each call only goes into children, so it stops at the leaves, and each position in the two trees is visited at most once. The price of the shortcut is that the patch list isn't always the shortest. A list item that moved, or a type change around similar content like the li items in the trace, produces more work than needed. Keys fix the first case.

Going deeper

3 more ideas

Why different types replace the whole subtree

A ul and an ol, or a Form and a Spinner component, rarely share inner structure. Comparing inside them would cost time and almost never find anything to keep. React's rule is to destroy the old subtree, including any state in it, and build the new one. That is why changing a component's type resets its state.

Why keys matter

Matching children by position goes wrong when items are inserted at the front of a list: every item shifts, so every pair looks different. With a key, the diff matches old and new children by key, so it sees that the old items are all still there and only one was added. React warns when list items have no key for this reason. Some libraries, like Vue 3 and Inferno, also use a longest increasing subsequence of the kept items to move as few DOM nodes as possible.

How fast it is

Each node of the old and new trees is visited at most once, and each prop is compared once. That is O(n + p) for n nodes and p props. The recursion goes as deep as the tree, so extra memory is O(depth) plus the patch list.

Work it by hand

Every step in a table, with why

Diff a shopping cart before and after an update. Every kind of patch appears once, and the replaced list's items are never looked at.

old = section{id: "cart"}[h3[span{class: "count"}], ul{class: "items"}[li, li], p{hidden: "yes"}], new = section{id: "cart", class: "open"}[h3, ol{class: "items"}[li, li], p, button{type: "submit"}]

SteppatholdNodenewNodePatch pushedWhy
10sectionsection["prop", "0", "class", "open"]Same type. keys is id and class. id is equal; class is new. Then it compares Math.max(3, 4) = 4 child positions.
20.0h3h3noneSame type and no props. The old h3 has 1 child and the new one has 0, so it checks 1 position.
30.0.0spanundefined["remove", "0.0.0"]There is no new node at this position, so the old span must go.
40.1ulol["replace", "0.1", "ol"]The types differ, so the whole subtree is replaced. The two li children inside are never compared, even though they look the same.
50.2pp["prop", "0.2", "hidden", null]Same type. hidden is missing from the new props, so it is sent as null, meaning remove it.
60.3undefinedbutton["insert", "0.3", "button"]There was no fourth child before, so the button is inserted. This was the last position, so the diff ends.

5 patches from 6 calls of diff. Each tree has 7 nodes, but the 2 li nodes on each side were skipped because their parent was replaced.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Virtual DOM diffingO(n + p)O(depth)You re-describe the whole UI on each change and want to keep the real elements, focus, and state, at linear cost.
Rebuild everything with innerHTMLO(n)O(n)The first render, or static content with no state to keep. It is simple but resets focus, input values, and scroll.
Exact tree edit distanceO(n^3)O(n^2)Offline tools on small trees, such as comparing two XML files, where the truly smallest edit list matters more than speed.
Fine-grained updates (signals)O(k)O(n)You can track which k values changed and which nodes use them, so updates touch only those nodes, as in Solid or Svelte.

Extra memory: O(depth) for the recursion, one call per level of the tree. The patches list can grow to O(n + p) in the worst case.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Virtual DOM diffing and the other approaches, on a scale where each line up is 10 times more steps.
  • Virtual DOM diffing O(n + p)
  • Rebuild everything with innerHTML, Fine-grained updates (signals) O(n)
  • Exact tree edit distance O(n^3)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Virtual DOM diffing202,0002 million
Rebuild everything with innerHTML101,0001 million
Exact tree edit distance1,0001 billionmore than a quadrillion
Fine-grained updates (signals)101,0001 million

Inputs that need care

6 tricky inputs
Both trees are empty: diff(undefined, undefined)
The first branch runs and reads newNode.type, which throws a TypeError. Add if (!oldNode && !newNode) return patches; at the top. Inside the recursion this can't happen, because one of the two lists always has a child at index i.
The same tree twice
Every type and every prop is equal, so the result is []. This is the common case that must be fast.
An item is added at the front of an unkeyed list: [A, B, C] becomes [Z, A, B, C]
Positions are compared, so it pushes 3 prop patches (A to Z, B to A, C to B) and one insert at the end. With 100 items it is 101 patches for a single new item. Keys fix this.
Two children are removed from the end: [A, B, C, D] becomes [A, B]
It pushes remove 0.2 then remove 0.3. If you apply them in that order, removing index 2 shifts the old index 3 down, so apply removes from the highest index down, or look up all nodes before changing anything.
A prop whose value is a new object each time, like style: { color: "red" }
!== compares references, so it always looks changed and a patch is pushed every time. React's DOM renderer compares style objects key by key, and useMemo keeps the same object between renders.
Text children, like the string "Hello"
This code expects every child to have type, props, and children. Real libraries treat text as its own kind of node and compare the strings themselves.

Variations and follow-ups

Twists interviewers add

Keyed children

Put the old children in a Map by key. For each new child, look up the old child with the same key and diff the two, wherever they sit. Old children whose key no longer appears are removed. React then decides which DOM nodes to move by tracking the last kept position, and Vue 3 finds a longest increasing subsequence of the kept items, which keeps the largest set of nodes in place and moves the rest.

Two pointers at both ends

Snabbdom, and Vue 2 which was based on it, compare the children with four pointers: the start and end of the old list and of the new list. Common edits like adding at the front, removing from the end, or reversing are caught in one pass before any map is needed.

Skipping unchanged components

React.memo and shouldComponentUpdate let a component say "my props didn't change", so the whole subtree below it is skipped. Then the diff costs time in proportion to what changed, not to the size of the page.

No virtual DOM at all

Svelte and Solid compile templates into code that knows which DOM node shows which value. When a value changes, they update that node directly, so there is no tree to diff.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "two versions of a tree", "list the patches", "same type means update", or a mention of keys. The output is usually a list of operations with paths.
  • Explain the two rules and why they are guesses: exact tree diffing is about O(n^3), and these rules give O(n) because UI updates rarely move nodes between parents.
  • Test by hand: a root whose type changes, a child added at the end, a child removed, and a prop that disappears. The last one catches code that only loops over the new props.
  • Expect the follow-up "how would keys change your children loop?". Answer: map old children by key, diff each new child against the old child with the same key, remove the old ones that weren't used, and then move nodes into the new order.

Where frontend code uses it

The same idea in real UI code
  • React's reconciliation follows these two rules: elements of different types produce different trees, and key tells React which children are the same between renders.
  • Vue, Preact, and Inferno each diff virtual nodes with similar rules, and Vue 3 moves keyed children using a longest increasing subsequence.
  • Libraries that patch the real DOM directly, like morphdom, compare an old and new DOM tree with the same same-type-means-update idea.

Related algorithms