Virtual DOM Diffing Algorithm in React
The Virtual DOM Diffing Algorithm is the process React uses to determine what has changed in the UI and update only the necessary parts of the real DOM instead of re-rendering everything.
What is the Virtual DOM?
The Virtual DOM (VDOM) is a lightweight JavaScript representation of the actual browser DOM.
Instead of directly modifying the browser DOM, React:
- Creates a Virtual DOM tree.
- Compares it with the previous Virtual DOM tree.
- Finds the differences (diffing).
- Updates only the changed parts in the real DOM (reconciliation).
Why is Diffing Needed?
Updating the browser’s DOM is relatively expensive because it can trigger:
- Layout recalculation
- Painting
- Reflow
- Browser rendering work
React minimizes these costly operations by updating only what has actually changed.
How the Diffing Algorithm Works
State Changes
│
▼
Render Function Executes
│
▼
New Virtual DOM Tree
│
▼
Compare with Previous Virtual DOM
│
▼
Find Differences (Diffing)
│
▼
Generate Minimal DOM Updates
│
▼
Update Real DOM
Example
| Change Type | Before | After | React Detects | Real DOM Update |
|---|---|---|---|---|
| Text Change | <h1>Hello</h1> | <h1>Hello React</h1> | The text content has changed, but the element type (h1) is the same. | Updates only the text node. The existing <h1> element is reused. |
| Attribute Change | <button disabled={false}>Save</button> | <button disabled={true}>Save</button> | Only the disabled attribute has changed. | Updates only the disabled attribute. The button element and its children remain unchanged. |
| Element Type Change | <div>Hello</div> | <span>Hello</span> | The root element type has changed (div → span). | Removes the old <div> and creates a new <span> along with its entire subtree. |
| Child Addition | A, B | A, B, C | A new child node has been added at the end of the list. | Creates and appends only the new child node (C). Existing nodes (A, B) are reused. |
| Child Removal | A, B, C | A, C | The child node B no longer exists. | Removes only the DOM node for B. Remaining nodes are preserved. |
| List Reordering (with keys) | A, B, C | C, A, B | The same list items exist but their positions have changed. React identifies each item using its key. | Moves the existing DOM nodes to their new positions instead of destroying and recreating them. |
| List Reordering (without keys) | A, B, C | C, A, B | React compares items by their position because no stable keys are available. | May update or recreate multiple DOM nodes unnecessarily, leading to extra rendering work and loss of component state. |
Points to Remember
| Scenario | React Detects | Real DOM Impact |
|---|---|---|
| Same element type | Compare props and children | Update only what changed |
| Different element type | Entire subtree is different | Replace the whole subtree |
| Same text node | Text value changed | Update only the text |
| Attribute change | Only attribute differs | Update only that attribute |
| New child | Child inserted | Append new DOM node |
| Removed child | Child deleted | Remove only that DOM node |
Stable key | Same item, different position | Reuse and move existing DOM nodes |
Missing key | Cannot reliably identify items | May recreate multiple DOM nodes and trigger unnecessary re-renders |
Time Complexity
| Algorithm | Complexity |
|---|---|
| Naive tree comparison | O(n³) |
| React Diffing Algorithm | Approximately O(n) |
React achieves this improvement by assuming:
- Different element types represent different trees.
- Stable
keyprops uniquely identify children.
Naive tree comparison O(n³)
A general tree comparison algorithm computes the Tree Edit Distance, similar to how string edit distance compares two strings.
For n nodes:
- There are O(n²) possible pairs of nodes to compare.
- For each pair, the algorithm may perform O(n) additional work to determine the optimal sequence of edits.
So the total work becomes:
O(n²) × O(n) = O(n³)
This is why a generic tree diff algorithm has cubic time complexity.
React Diffing Algorithm O(n)
React makes two assumptions:
- Different element types create different trees.
<div /> → <section />
React immediately replaces the subtree instead of trying to find the optimal edit sequence.
- Keys uniquely identify children.
<li key="1">A</li><li key="2">B</li>
Instead of comparing every child with every other child, React uses the keys to directly match corresponding elements.
With these assumptions, React can process the tree in a single traversal. So the work is approximately proportional to the number of nodes: Time ≈ O(n)
Best Practices
- Use stable, unique
keyvalues for list items. - Avoid using array indexes as keys if items can be reordered, inserted, or deleted.
- Keep component trees predictable to help React reuse existing elements efficiently.
- Prevent unnecessary re-renders with techniques like
React.memo,useMemo, anduseCallbackwhen appropriate.
