Implement Virtual DOM Diff and Patch

Why Build a Virtual DOM?

Every frontend interview at a top company eventually asks some version of: "How does React update the DOM efficiently?" You can memorize the answer, or you can build the thing and never forget it.

Here's the deal — the real DOM is slow. Not because the DOM API is poorly designed, but because touching the DOM triggers expensive browser work: style recalculation, layout, paint, and compositing. The fewer DOM operations you make, the faster your app feels. The Virtual DOM is an abstraction that lets you describe what the UI should look like, then figures out the minimum set of real DOM changes needed to get there.

We're going to build the whole pipeline: create virtual nodes, render them to real DOM, diff two virtual trees, and patch the real DOM with only the changes.

Step 1: createElement — Building Virtual Nodes

A virtual node (vnode) is just a plain JavaScript object that describes a DOM element. No magic, no classes — just data.

function createElement(type, props, ...children) {
  return {
    type,
    props: props || {},
    children: children
      .flat()
      .map(child =>
        typeof child === 'object' ? child : createTextNode(child)
      ),
  };
}

function createTextNode(text) {
  return {
    type: 'TEXT',
    props: {},
    children: [],
    value: String(text),
  };
}

Usage looks like this:

const vnode = createElement(
  'div',
  { id: 'app', className: 'container' },
  createElement('h1', null, 'Hello'),
  createElement('p', null, 'World'),
);

That produces a tree like:

{
  type: 'div',
  props: { id: 'app', className: 'container' },
  children: [
    {
      type: 'h1',
      props: {},
      children: [{ type: 'TEXT', props: {}, children: [], value: 'Hello' }]
    },
    {
      type: 'p',
      props: {},
      children: [{ type: 'TEXT', props: {}, children: [], value: 'World' }]
    }
  ]
}

Notice how text content becomes a special TEXT node. This simplifies everything downstream because every node in the tree has the same shape — either an element or a text node. No special cases leaking everywhere.

Step 2: render — Virtual Nodes to Real DOM

Now we need a function that takes a vnode and creates actual DOM elements.

function render(vnode) {
  if (vnode.type === 'TEXT') {
    return document.createTextNode(vnode.value);
  }

  const el = document.createElement(vnode.type);

  for (const [key, val] of Object.entries(vnode.props)) {
    if (key.startsWith('on')) {
      const event = key.slice(2).toLowerCase();
      el.addEventListener(event, val);
    } else if (key === 'className') {
      el.setAttribute('class', val);
    } else {
      el.setAttribute(key, val);
    }
  }

  for (const child of vnode.children) {
    el.appendChild(render(child));
  }

  return el;
}

To mount the whole tree:

function mount(vnode, container) {
  const dom = render(vnode);
  container.appendChild(dom);
  return dom;
}

Step 3: The Diff Algorithm

This is where it gets interesting. The diff function compares an old vnode tree with a new vnode tree and produces a list of patches — minimal instructions for updating the real DOM.

Patch types

const PATCH = {
  CREATE: 'CREATE',
  REMOVE: 'REMOVE',
  REPLACE: 'REPLACE',
  UPDATE: 'UPDATE',
};

The core diff function

function diff(oldNode, newNode) {
  if (!oldNode) {
    return { type: PATCH.CREATE, newNode };
  }

  if (!newNode) {
    return { type: PATCH.REMOVE };
  }

  if (changed(oldNode, newNode)) {
    return { type: PATCH.REPLACE, newNode };
  }

  if (newNode.type !== 'TEXT') {
    return {
      type: PATCH.UPDATE,
      props: diffProps(oldNode.props, newNode.props),
      children: diffChildren(oldNode.children, newNode.children),
    };
  }

  return null;
}

Detecting changes

function changed(a, b) {
  if (a.type !== b.type) return true;
  if (a.type === 'TEXT' && b.type === 'TEXT') {
    return a.value !== b.value;
  }
  return false;
}

The changed function answers a simple question: is this a completely different node? If the types differ (a div became a span), or text content changed, we need a full replacement. Otherwise, we dig deeper into props and children.

Diffing props

function diffProps(oldProps, newProps) {
  const patches = [];

  for (const [key, val] of Object.entries(newProps)) {
    if (oldProps[key] !== val) {
      patches.push({ key, value: val });
    }
  }

  for (const key of Object.keys(oldProps)) {
    if (!(key in newProps)) {
      patches.push({ key, value: undefined });
    }
  }

  return patches;
}

Two passes: first, find props that are new or changed. Second, find props that were removed. Removed props get undefined as a sentinel value.

Diffing children (unkeyed)

function diffChildren(oldChildren, newChildren) {
  const patches = [];
  const maxLen = Math.max(oldChildren.length, newChildren.length);

  for (let i = 0; i < maxLen; i++) {
    patches.push(diff(oldChildren[i], newChildren[i]));
  }

  return patches;
}

This is the naive version — it compares children by index. We'll upgrade this with keys shortly, but first let's understand why this approach breaks down.

Step 4: patch — Applying Changes to the Real DOM

The patch function takes the patches generated by diff and applies them to the actual DOM.

function patch(parent, patches, index = 0) {
  const el = parent.childNodes[index];

  if (!patches) return;

  switch (patches.type) {
    case PATCH.CREATE: {
      parent.appendChild(render(patches.newNode));
      return;
    }

    case PATCH.REMOVE: {
      parent.removeChild(el);
      return;
    }

    case PATCH.REPLACE: {
      parent.replaceChild(render(patches.newNode), el);
      return;
    }

    case PATCH.UPDATE: {
      patchProps(el, patches.props);
      patchChildren(el, patches.children);
      return;
    }
  }
}

Patching props

function patchProps(el, propPatches) {
  for (const { key, value } of propPatches) {
    if (key.startsWith('on')) {
      const event = key.slice(2).toLowerCase();
      if (value) {
        el.addEventListener(event, value);
      } else {
        el.removeEventListener(event, value);
      }
    } else if (value === undefined) {
      el.removeAttribute(key === 'className' ? 'class' : key);
    } else {
      el.setAttribute(key === 'className' ? 'class' : key, value);
    }
  }
}

Patching children

function patchChildren(parent, childPatches) {
  for (let i = 0; i < childPatches.length; i++) {
    patch(parent, childPatches[i], i);
  }
}

Keyed Reconciliation — The Missing Piece

The unkeyed algorithm compares children strictly by index. This means reordering, inserting, or removing items in the middle of a list causes unnecessary DOM mutations. Keys solve this by giving each child a stable identity.

How keyed diff works

function diffChildrenKeyed(oldChildren, newChildren) {
  const oldKeyMap = new Map();
  oldChildren.forEach((child, i) => {
    const key = child.props.key;
    if (key != null) oldKeyMap.set(key, i);
  });

  const patches = [];
  const usedOldIndices = new Set();

  for (let i = 0; i < newChildren.length; i++) {
    const newChild = newChildren[i];
    const key = newChild.props.key;

    if (key != null && oldKeyMap.has(key)) {
      const oldIndex = oldKeyMap.get(key);
      usedOldIndices.add(oldIndex);
      const childPatch = diff(oldChildren[oldIndex], newChild);
      patches.push({
        type: 'REORDER',
        from: oldIndex,
        to: i,
        patch: childPatch,
      });
    } else {
      patches.push({ type: PATCH.CREATE, newNode: newChild });
    }
  }

  for (let i = oldChildren.length - 1; i >= 0; i--) {
    if (!usedOldIndices.has(i)) {
      patches.push({ type: PATCH.REMOVE, index: i });
    }
  }

  return patches;
}

The strategy:

1. Build a map from key to old index
2. Walk the new children — if a key exists in the old map, reuse that node (and diff its subtree). If not, it is a new node
3. Any old index not referenced in the new list is a removal

Putting It All Together

Here is the complete update cycle:

let currentVDOM = null;
let rootDOM = null;

function update(newVDOM) {
  if (!currentVDOM) {
    rootDOM = render(newVDOM);
    document.getElementById('root').appendChild(rootDOM);
  } else {
    const patches = diff(currentVDOM, newVDOM);
    patch(document.getElementById('root'), patches, 0);
  }
  currentVDOM = newVDOM;
}

Every time you call update with a new virtual tree, the system:

1. Diffs the old tree against the new tree
2. Generates minimal patches
3. Applies those patches to the real DOM
4. Stores the new tree as the current state

This is the core loop behind every virtual DOM library. React wraps this in a component model with setState and hooks. Preact keeps it minimal. Vue uses reactive proxies to trigger it automatically. But under the hood, they all do the same dance: build a new virtual tree, diff it, patch the DOM.

Complexity Analysis

The naive tree diff algorithm (comparing every node with every other node) is O(n^3). That is completely unusable for real apps with thousands of nodes.

React's diff algorithm runs in O(n) by making two assumptions:

1. Different types produce different trees. If a div becomes a span, React tears down the entire subtree and rebuilds it. No point diffing children of two completely different element types.

2. Keys identify children across renders. Within a list, keys tell React which children are "the same" so it can reorder instead of recreate.

These heuristics drop the complexity from O(n^3) to O(n). In practice, they are correct almost 100% of the time. The rare case where they are wrong (a div changed to a section but kept identical children) costs a subtree rebuild — still fast because subtrees are typically small.

Handling Edge Cases

Text node updates

When a text node changes, there is no need to remove and recreate it. You can update the nodeValue property directly, which is faster than replaceChild:

if (patches.type === PATCH.REPLACE && patches.newNode.type === 'TEXT') {
  el.nodeValue = patches.newNode.value;
  return;
}

Element type changes

When type changes (say, div to section), the entire subtree must be replaced. There is no way to morph a div into a section — the browser does not support it. You have to create a new element and re-render all children.

Boolean and null children

JSX expressions like {showHeader && <Header />} can produce false, null, or undefined. Filter these out in createElement:

function createElement(type, props, ...children) {
  return {
    type,
    props: props || {},
    children: children
      .flat()
      .filter(child => child != null && child !== false && child !== true)
      .map(child =>
        typeof child === 'object' ? child : createTextNode(child)
      ),
  };
}

Event handler updates

Our naive approach has a subtle bug — calling addEventListener with a new handler does not replace the old handler. It adds a second one. A production VDOM stores the current handler reference and removes it before adding the new one:

function patchEvent(el, eventName, oldHandler, newHandler) {
  if (oldHandler) {
    el.removeEventListener(eventName, oldHandler);
  }
  if (newHandler) {
    el.addEventListener(eventName, newHandler);
  }
}

React avoids this entirely by using event delegation — a single listener on the root that dispatches based on the target element. Fewer listeners, easier cleanup, better memory usage.

What React Does Differently

Our implementation covers the core concepts, but React's reconciler (called Fiber) adds several layers on top:

Fiber architecture. Instead of diffing the tree in one synchronous pass, React breaks work into small chunks (fibers) that can be paused and resumed. This prevents long renders from blocking the main thread.

Concurrent rendering. React can prepare multiple versions of the UI simultaneously and commit whichever one is ready, discarding the rest.

Synthetic events. Instead of attaching listeners to individual DOM nodes, React delegates all events to the root and dispatches them through its own system. This gives it full control over event timing and batching.

Component-level diffing. React diffs at the component boundary first. If a component's props and state have not changed (via memo, useMemo, or the React Compiler), React skips that entire subtree without even calling the render function.

Batched updates. Multiple setState calls within the same event handler produce a single re-render, not one per call. This was opt-in in React 17 and is automatic in React 18+.

Interview Tips

When an interviewer asks you to implement a virtual DOM, they want to see that you understand the architecture, not that you memorized 200 lines of code. Focus on:

1. Start with the data model. Define what a vnode looks like before you write any logic. Show the interviewer you think about data structures first.

2. Explain the three phases clearly. Build the virtual tree (createElement) → Diff old vs new (generate patches) → Patch the real DOM (apply patches). Each phase has a single responsibility.

3. Talk about tradeoffs. Why O(n) instead of O(n^3)? What do we lose? (Cross-level moves are not detected.) Why is that acceptable? (They almost never happen in practice.)

4. Mention keys proactively. Do not wait for the interviewer to ask "what about list reordering?" Show you know the problem exists and how keys solve it.

5. Connect to React. After building the basic version, explain what React adds on top: Fiber, concurrent rendering, batching. This shows you understand the real system, not just a toy version.