Lesson 13-Complex Frontend Algorithms

Virtual DOM Diffing Algorithm (The Heart of React)

What the Virtual DOM Is and Why It Exists

Before we can understand the diffing algorithm, we need to understand why the virtual DOM exists in the first place.

In the early days of frontend development, we manipulated the DOM directly. jQuery made this easier, but it was still fundamentally imperative: you selected elements and changed them. The problem wasn’t just that this was tedious—it was that the DOM is slow.

Let me be precise about this. The DOM itself isn’t slow—what’s slow is that reading from or writing to the DOM causes layout recalculation, style recomputation, and repainting. These are expensive operations. If you’re making dozens of DOM updates in a loop, the browser might recalculate layout dozens of times.

The virtual DOM is React’s solution to this problem. Here’s the mental model:

  1. You describe what you want the UI to look like (your React component’s render output)
  2. React creates a virtual DOM tree—a lightweight JavaScript object representation of the actual DOM
  3. When state changes, React creates a new virtual DOM tree
  4. React diffs the old tree and the new tree to determine what actually changed
  5. React batches all the necessary DOM updates and applies them in a single pass

The key insight here is batching. By computing the minimal set of DOM updates and applying them all at once, React minimizes the number of expensive DOM operations.

But here’s the thing that most explanations get wrong: the virtual DOM isn’t faster than direct DOM manipulation because of the diffing. It’s faster because of the batching and minimization of DOM operations. The diffing algorithm is just the mechanism that determines what needs to be updated.

Let’s look at what a virtual DOM node actually looks like:

// This is what React creates when you write <div className="hello">World</div>
const virtualDOMNode = {
  type: 'div',
  props: {
    className: 'hello',
    children: 'World'
  },
  key: null,
  ref: null,
  // ... internal React properties
};

When you have a component that renders a tree of elements, React builds a tree of these virtual DOM nodes. It’s just a JavaScript object—no magic, no special data structure. The power comes from being able to compare two of these trees efficiently.

The Diffing Algorithm Explained Step by Step

Now we get to the heart of the matter. Given two trees—the old virtual DOM tree and the new virtual DOM tree—how do we determine what changed?

The naive approach would be to compare every node in the old tree to every node in the new tree. That’s an O(n³) algorithm, which is completely unacceptable for UI rendering where n might be hundreds or thousands of nodes.

React’s diffing algorithm achieves O(n) complexity. That’s a massive improvement. But how?

The secret is constraints. React makes two assumptions that allow for linear-time diffing:

  1. Different element types produce different trees. If you go from <div> to <span>, React won’t even try to reuse the DOM node—it will tear down the entire subtree and build a new one.
  2. Updates can be guided by keys. When rendering lists, you provide a key prop that helps React identify which items have changed, been added, or been removed.

With these constraints, the diffing algorithm becomes a single pass through the tree. Here’s the algorithm at a high level:

function diff(oldTree, newTree, parentDOMNode):
  // Compare the root nodes
  if (oldTree.type !== newTree.type):
    // Type changed - replace the entire subtree
    replaceSubtree(parentDOMNode, oldTree, newTree)
    return
  
  // Type is the same - update properties
  updateProps(oldTree.props, newTree.props, parentDOMNode)
  
  // Now diff the children
  diffChildren(oldTree.children, newTree.children, parentDOMNode)

The real complexity is in diffChildren. When the children are simple text nodes, it’s easy—just update the text content. But when children are arrays of virtual DOM nodes (which is what happens when you render a list of components), we need a smarter algorithm.

Here’s where keys become critical. Without keys, React uses the positional approach: it assumes that the first child in the old tree corresponds to the first child in the new tree, the second to the second, and so on. If you insert an item at the beginning of a list, React will re-render every item in that list because it thinks every item has changed.

With keys, React builds a map from key to child node. When diffing, it looks up each new child’s key in the map to find its corresponding old child. This allows React to detect when items have moved (been reordered) versus when they’ve actually changed.

Let me show you the actual algorithm for diffing children with keys:

function diffChildren(oldChildren, newChildren, parentDOMNode) {
  // Build a map of old children by key
  const oldKeyedChildren = new Map();
  for (const child of oldChildren) {
    if (child.key != null) {
      oldKeyedChildren.set(child.key, child);
    }
  }
  
  // Track which old children have been reused
  const reusedKeys = new Set();
  
  // Diff each new child against the old children
  for (let i = 0; i < newChildren.length; i++) {
    const newChild = newChildren[i];
    const oldChild = newChild.key != null 
      ? oldKeyedChildren.get(newChild.key) 
      : oldChildren[i]; // Positional fallback
    
    if (oldChild) {
      // We found a match - diff these two nodes
      diff(oldChild, newChild, parentDOMNode);
      if (newChild.key != null) {
        reusedKeys.add(newChild.key);
      }
    } else {
      // No match - this is a new node
      createNewDOMNode(newChild, parentDOMNode, i);
    }
  }
  
  // Remove old children that weren't reused
  for (const [key, oldChild] of oldKeyedChildren) {
    if (!reusedKeys.has(key)) {
      removeDOMNode(oldChild, parentDOMNode);
    }
  }
}

This is a simplified version, but it captures the essential logic. The real React algorithm is more complex because it also handles cases like children without keys, children with mixed keyed and non-keyed elements, and various edge cases around refs and component lifecycle.

Tree Comparison with O(n) Complexity

Let’s dig deeper into why this algorithm is O(n).

In the worst case, a tree comparison algorithm needs to compare every node in the old tree to every node in the new tree. If the trees have n nodes each, that’s n × n = n² comparisons. And if you’re doing subtree moves (where a node and all its children move to a different parent), you need to consider all possible mappings, which gives you O(n³) in the general case.

React achieves O(n) by imposing constraints on what kinds of changes are possible:

  1. Only compare nodes at the same level. React never “moves” a node from one part of the tree to another part. If a node appears in a different position, React treats it as a deletion plus a creation. This constraint alone eliminates the need to consider cross-level moves, which is what makes the general tree diffing problem O(n³).
  2. Different element types = different trees. If the element type changes (div → span, or ComponentA → ComponentB), React doesn’t even try to diff the subtrees. It just destroys the old DOM node and creates a new one. This might seem wasteful, but it’s actually optimal because:
    • The cost of diffing is avoided
    • Component cleanup (lifecycle methods, event handlers) happens correctly
    • The overall complexity remains O(n) because each node is still only visited once
  3. Keys provide identity. When you provide a key, React can track a node’s identity across renders. This means React can detect when a node moved within its siblings (not across levels) and update the DOM accordingly.

Let me illustrate this with a concrete example. Suppose you have a list:

// Old tree
<ul>
  <li key="A">Item A</li>
  <li key="B">Item B</li>
  <li key="C">Item C</li>
</ul>

// New tree (B moved to the end)
<ul>
  <li key="A">Item A</li>
  <li key="C">Item C</li>
  <li key="B">Item B</li>
</ul>

Without keys, React would see:

  • Position 0: A → A (same, no update)
  • Position 1: B → C (different, update)
  • Position 2: C → B (different, update)

With keys, React sees:

  • A is at position 0 in both (no move)
  • C moved from position 2 to position 1
  • B moved from position 1 to position 2

React can update the DOM to reflect these moves without recreating the nodes. The algorithm for this is essentially a longest increasing subsequence algorithm applied to the positions of the keys. React finds the minimum number of DOM moves needed to transform the old ordering into the new ordering.

Here’s a more detailed implementation of the keyed diff algorithm:

function diffKeyedChildren(oldChildren, newChildren, parentDOMNode) {
  // Build index of old children by key
  const oldIndex = new Map();
  for (let i = 0; i < oldChildren.length; i++) {
    const child = oldChildren[i];
    if (child.key != null) {
      oldIndex.set(child.key, { child, index: i });
    }
  }
  
  // Track the last placed index to maintain order
  let lastPlacedIndex = 0;
  
  // Process new children
  for (let i = 0; i < newChildren.length; i++) {
    const newChild = newChildren[i];
    const oldEntry = oldIndex.get(newChild.key);
    
    if (oldEntry) {
      // This child existed before - it may have moved
      if (oldEntry.index < lastPlacedIndex) {
        // This child needs to be moved
        moveDOMNode(oldEntry.child, parentDOMNode, i);
      } else {
        // This child is already in the right position (or close enough)
        lastPlacedIndex = oldEntry.index;
      }
      
      // Diff the content of this child
      diff(oldEntry.child, newChild, parentDOMNode);
      
      // Mark as processed
      oldIndex.delete(newChild.key);
    } else {
      // New child - insert it
      createNewDOMNode(newChild, parentDOMNode, i);
    }
  }
  
  // Remove any old children that weren't processed
  for (const [key, { child }] of oldIndex) {
    removeDOMNode(child, parentDOMNode);
  }
}

The lastPlacedIndex trick is important. It ensures that we maintain the correct order in the DOM. If a child’s old index is less than lastPlacedIndex, it means we’ve already placed a child that was originally after it, so this child needs to be moved to maintain order.

Bailing Out of Diffing (shouldComponentUpdate Equivalent)

One of the most important optimizations in React’s diffing algorithm is the ability to bail out of diffing entirely for subtrees that haven’t changed.

Every React component (both class components and function components with React.memo) has a mechanism to determine whether it needs to re-render. For class components, this is shouldComponentUpdate. For function components, this is React.memo. For the virtual DOM diffing algorithm itself, this is the shallow comparison of props and state.

The logic is simple but powerful:

function shouldUpdateComponent(oldProps, newProps, oldState, newState):
  // Compare each prop (shallow comparison)
  for (const key in newProps):
    if (oldProps[key] !== newProps[key]):
      return true  // Prop changed - need to re-render
  
  // Compare state
  for (const key in newState):
    if (oldState[key] !== newState[key]):
      return true  // State changed - need to re-render
  
  return false  // Nothing changed - bail out

If shouldUpdateComponent returns false, React skips the diffing for that component’s entire subtree. This is a massive performance optimization for large applications.

But there’s a subtlety here that confuses many developers: shallow comparison. The === check in JavaScript compares references, not values. So if you pass an object as a prop, and you create a new object with the same values, React will see it as a change:

// This will cause a re-render even though the values are the same
<MyComponent config={{ width: 100, height: 200 }} />

// Every render creates a new object, so props.config is always "different"

This is why React best practices recommend:

  • Using primitive values (strings, numbers, booleans) as props when possible
  • Using useMemo or useCallback to memoize objects and functions
  • Using immutable data structures (like those from Immutable.js) where structural sharing ensures that unchanged parts have the same reference

Let’s implement a proper shallowEqual function that React actually uses:

function shallowEqual(objA, objB) {
  if (Object.is(objA, objB)) {
    return true; // Same reference or same primitive value
  }
  
  if (
    typeof objA !== 'object' || objA === null ||
    typeof objB !== 'object' || objB === null
  ) {
    return false; // One is not an object (and they weren't equal above)
  }
  
  const keysA = Object.keys(objA);
  const keysB = Object.keys(objB);
  
  if (keysA.length !== keysB.length) {
    return false; // Different number of keys
  }
  
  // Check that every key in A exists in B and has the same value
  for (let i = 0; i < keysA.length; i++) {
    const key = keysA[i];
    if (!Object.prototype.hasOwnProperty.call(objB, key)) {
      return false; // Key in A doesn't exist in B
    }
    if (!Object.is(objA[key], objB[key])) {
      return false; // Value changed
    }
  }
  
  return true;
}

Notice the use of Object.is instead of ===. Object.is handles two edge cases that === doesn’t:

  • Object.is(NaN, NaN) returns true (whereas NaN !== NaN)
  • Object.is(0, -0) returns false (whereas 0 === -0)

These edge cases rarely matter in practice, but React uses Object.is for correctness.

Keys and Their Importance in Diffing

I’ve mentioned keys several times already, but they’re important enough to deserve their own deep dive.

What problem do keys solve?

When React renders a list of elements, it needs to track which element is which across renders. The default behavior (using positional indexing) works fine for static lists, but breaks down when the list can change.

Consider this example:

// Render 1
<ul>
  <li>Alice</li>
  <li>Bob</li>
</ul>

// Render 2 (insert "Charlie" at the beginning)
<ul>
  <li>Charlie</li>
  <li>Alice</li>
  <li>Bob</li>
</ul>

Without keys, React sees:

  • Position 0: Alice → Charlie (different, update DOM)
  • Position 1: Bob → Alice (different, update DOM)
  • Position 2: (nothing) → Bob (new, create DOM)

React will update every single <li> element, even though we only inserted one item. With 1000 items in the list, inserting at the beginning would cause 1000 DOM updates.

With keys:

// Render 1
<ul>
  <li key="alice">Alice</li>
  <li key="bob">Bob</li>
</ul>

// Render 2
<ul>
  <li key="charlie">Charlie</li>
  <li key="alice">Alice</li>
  <li key="bob">Bob</li>
</ul>

React sees:

  • “charlie” is new → create DOM node
  • “alice” existed at position 0, now at position 1 → move DOM node
  • “bob” existed at position 1, now at position 2 → move DOM node

React can move the existing DOM nodes instead of recreating them. This is much faster.

What makes a good key?

A good key is:

  1. Unique among siblings (required – React will warn if not)
  2. Stable (doesn’t change between renders)
  3. Predictable (not random)
  4. Not array index (unless the list is static and never reordered)

The worst key you can use is Math.random():

// NEVER DO THIS
{items.map(item => <li key={Math.random()}>...</li>)}

Every render, every item gets a new random key. React thinks every item is “new” and recreates all the DOM nodes. This defeats the entire purpose of keys.

Using array index as a key is also problematic when the list can be reordered:

// Problematic if list can be reordered
{items.map((item, index) => <li key={index}>...</li>)}

If you insert an item at the beginning, all subsequent items get a new index, so React thinks all of them changed.

The best key is a stable ID from your data:

// Good
{items.map(item => <li key={item.id}>...</li>)}

How keys work internally

When React encounters a list of children with keys, it builds a map data structure (a JavaScript Map or object) that maps keys to their corresponding fiber nodes (or virtual DOM nodes in the old architecture). This map allows O(1) lookup of a child by its key.

The algorithm then processes the new children in order, looking up each one in the map. If found, the child is reused (and possibly moved). If not found, it’s created. After processing all new children, any old children still in the map are deleted.

Implementation of a Simplified Diffing Algorithm

Let’s bring everything together and implement a working (simplified) virtual DOM and diffing algorithm. This will help solidify your understanding.

// ============================================
// SIMPLIFIED VIRTUAL DOM IMPLEMENTATION
// ============================================

// A virtual DOM node
class VNode {
  constructor(type, props, children) {
    this.type = type;         // string (HTML tag) or function (component)
    this.props = props || {};  // object of props
    this.children = children || []; // array of VNode or strings
    this.key = props?.key || null; // key for diffing
  }
}

// Create a virtual DOM node (like React.createElement)
function h(type, props, ...children) {
  // Flatten children and filter out null/undefined
  const flatChildren = children
    .flat(Infinity)
    .filter(child => child != null && child !== false);
  
  return new VNode(type, props || {}, flatChildren);
}

// ============================================
// DIFFING ALGORITHM
// ============================================

function diff(oldVNode, newVNode, parentDOMNode, index = 0) {
  // Case 1: oldVNode doesn't exist → create new DOM node
  if (oldVNode == null) {
    const newDOMNode = createDOMNode(newVNode);
    parentDOMNode.appendChild(newDOMNode);
    return;
  }
  
  // Case 2: newVNode doesn't exist → remove old DOM node
  if (newVNode == null) {
    parentDOMNode.removeChild(parentDOMNode.childNodes[index]);
    return;
  }
  
  // Case 3: Both are text nodes
  if (typeof oldVNode === 'string' && typeof newVNode === 'string') {
    if (oldVNode !== newVNode) {
      parentDOMNode.childNodes[index].textContent = newVNode;
    }
    return;
  }
  
  // Case 4: Different types → replace entirely
  if (oldVNode.type !== newVNode.type) {
    const newDOMNode = createDOMNode(newVNode);
    parentDOMNode.replaceChild(newDOMNode, parentDOMNode.childNodes[index]);
    return;
  }
  
  // Case 5: Same type → update in place
  const domNode = parentDOMNode.childNodes[index];
  
  // Update props (simplified - only handles standard attributes)
  updateProps(domNode, oldVNode.props, newVNode.props);
  
  // Diff children
  diffChildren(oldVNode, newVNode, domNode);
}

function updateProps(domNode, oldProps, newProps) {
  // Remove old props that are not in newProps
  for (const key in oldProps) {
    if (!(key in newProps)) {
      domNode.removeAttribute(key);
    }
  }
  
  // Set new props (simplified - doesn't handle events, className, etc.)
  for (const key in newProps) {
    if (key === 'key' || key === 'children') continue;
    if (oldProps[key] !== newProps[key]) {
      if (key === 'className') {
        domNode.className = newProps[key];
      } else if (key.startsWith('on')) {
        // Event handler - simplified
        const eventName = key.toLowerCase().substring(2);
        domNode.addEventListener(eventName, newProps[key]);
      } else {
        domNode.setAttribute(key, newProps[key]);
      }
    }
  }
}

function diffChildren(oldVNode, newVNode, parentDOMNode) {
  const oldChildren = oldVNode.children;
  const newChildren = newVNode.children;
  
  // Check if children have keys
  const hasKeys = newChildren.some(child => child?.key != null);
  
  if (hasKeys) {
    diffKeyedChildren(oldChildren, newChildren, parentDOMNode);
  } else {
    // Simple positional diff
    const maxLength = Math.max(oldChildren.length, newChildren.length);
    for (let i = 0; i < maxLength; i++) {
      diff(oldChildren[i], newChildren[i], parentDOMNode, i);
    }
  }
}

function diffKeyedChildren(oldChildren, newChildren, parentDOMNode) {
  // Build map of old children by key
  const oldKeyMap = new Map();
  for (const child of oldChildren) {
    if (child?.key != null) {
      oldKeyMap.set(child.key, child);
    }
  }
  
  // Track which old children have been used
  const usedKeys = new Set();
  
  // Process new children
  for (let i = 0; i < newChildren.length; i++) {
    const newChild = newChildren[i];
    const key = newChild?.key;
    
    if (key != null && oldKeyMap.has(key)) {
      // Reuse existing child
      const oldChild = oldKeyMap.get(key);
      usedKeys.add(key);
      
      // Diff the reused child
      const existingDOMNode = findDOMNodeByKey(parentDOMNode, key);
      if (existingDOMNode) {
        // Move if necessary (simplified - doesn't actually move in this implementation)
        diff(oldChild, newChild, parentDOMNode, i);
      }
    } else {
      // New child (no key or key not found in old children)
      diff(undefined, newChild, parentDOMNode, i);
    }
  }
  
  // Remove old children that weren't used
  for (const [key, oldChild] of oldKeyMap) {
    if (!usedKeys.has(key)) {
      diff(oldChild, undefined, parentDOMNode, 0);
    }
  }
}

// ============================================
// DOM CREATION
// ============================================

function createDOMNode(vnode) {
  // Text node
  if (typeof vnode === 'string') {
    return document.createTextNode(vnode);
  }
  
  // Element node
  const domNode = document.createElement(vnode.type);
  
  // Set props
  for (const key in vnode.props) {
    if (key === 'key' || key === 'children') continue;
    if (key === 'className') {
      domNode.className = vnode.props[key];
    } else if (key.startsWith('on')) {
      const eventName = key.toLowerCase().substring(2);
      domNode.addEventListener(eventName, vnode.props[key]);
    } else {
      domNode.setAttribute(key, vnode.props[key]);
    }
  }
  
  // Create children
  for (const child of vnode.children) {
    domNode.appendChild(createDOMNode(child));
  }
  
  return domNode;
}

// ============================================
// USAGE EXAMPLE
// ============================================

// Create a virtual DOM tree
const vdom = h('div', { className: 'container' },
  h('h1', {}, 'Hello, Virtual DOM!'),
  h('ul', {},
    h('li', { key: 'a' }, 'Item A'),
    h('li', { key: 'b' }, 'Item B'),
    h('li', { key: 'c' }, 'Item C')
  )
);

// Render to actual DOM
const container = document.getElementById('root');
container.appendChild(createDOMNode(vdom));

// Now update with a new virtual DOM tree
const newVdom = h('div', { className: 'container' },
  h('h1', {}, 'Hello, Virtual DOM! (Updated)'),
  h('ul', {},
    h('li', { key: 'a' }, 'Item A'),
    h('li', { key: 'c' }, 'Item C'),
    h('li', { key: 'b' }, 'Item B (moved)') // Keys reordered!
  )
);

// Diff and update
diff(vdom, newVdom, container, 0);

This is a working (though simplified) implementation. The real React diffing algorithm has many more optimizations and edge case handling, but the core ideas are all here.

Virtual DOM Diff Process

Let me show you the virtual DOM diffing process visually:

flowchart TD
    A[Start: State Change Triggers Re-render] --> B[Render New Virtual DOM Tree]
    B --> C[Compare Old Tree and New Tree]
    C --> D{Are root nodes same type?}
    D -->|No| E[Replace Entire Subtree]
    D -->|Yes| F[Update Properties on DOM Node]
    F --> G[Diff Children]
    G --> H{Children have keys?}
    H -->|No| I[Positional Diff: Compare by Index]
    H -->|Yes| J[Keyed Diff: Build Map by Key]
    J --> K[Reuse Matching Nodes]
    K --> L[Move Nodes to Correct Position]
    L --> M[Remove Nodes Not in New Tree]
    I --> N[Update Text Nodes In-Place]
    I --> O[Recursively Diff Child Elements]
    E --> P[Create New DOM Nodes]
    P --> Q[Attach to DOM]
    N --> R[Batching: Collect All DOM Updates]
    O --> R
    M --> R
    Q --> R
    R --> S[Single Pass: Apply All Updates]
    S --> T[Browser Paints Once]
    
    style A fill:#e1f5fe
    style T fill:#c8e6c9
    style E fill:#ffcdd2
    style S fill:#fff9c4

This diagram shows the complete flow of React’s virtual DOM diffing algorithm. Notice how the algorithm always tries to minimize DOM operations, and how all updates are batched into a single pass.

Membership Required

You must be a member to access this content.

View Membership Levels

Already a member? Log in here

Course: Front-End Algorithms: Engineering & Practice
Share your love

Trending now

Exploring Web 3D Core Technologies Development
Assembly Language Programming From Low-Level Logic to System Kernel
WebRTC Advanced Guide：Media, Transport & Architecture
WebSocket Deep Guide：Building High-Performance Realtime Systems