Explain React's diffing algorithm in detail. How does it achieve O(n) complexity?

The Problem:

The generic algorithm for computing the minimum number of operations to transform one tree into another is O(n³). For a tree with 1,000 elements, that is 1 billion comparisons per update — far too expensive for a UI framework.

React's O(n) Solution — Two Heuristics:

React trades theoretical correctness for practical speed by assuming:

1. Different types produce different trees — If a <div> becomes a <span>, or a <Header> becomes a <Footer>, React does not attempt to match their children. It unmounts the entire old subtree (calling cleanup effects and componentWillUnmount) and mounts a completely new subtree.

2. Keys identify stable elements — When diffing children of the same parent, React uses key props to determine which children in the new list correspond to which children in the old list. This enables efficient handling of insertions, deletions, and reordering.

Three Scenarios During Diffing:

Scenario 1: Different Element Types When the root type changes (<div> → <article>, <ComponentA> → <ComponentB>), React tears down the entire old tree. All child components are unmounted, their state is destroyed, and cleanup effects run. Then a completely new tree is built from scratch.

Scenario 2: Same DOM Element Type When the type is the same (<div> → <div>), React keeps the same underlying DOM node and only updates the changed attributes. For example, changing className updates that one attribute. React then recurses into the children.

Scenario 3: Same Component Type When a component type is the same (<Counter> → <Counter>), React keeps the same component instance alive. The existing instance receives new props, state is preserved, and the component re-renders with updated props.

List Reconciliation With Keys:

Without keys, React matches children by index. Inserting at the beginning of a list shifts every index, causing React to update every child. With keys, React builds a map of key → element and matches by identity:

• Same key in both lists → keep the element, update props if needed
• Key in new list but not old → create new element
• Key in old list but not new → destroy the element

This makes insertions, deletions, and reordering all O(n).

Fiber Architecture (React 16+):

The Fiber tree is a linked list where each node has child, sibling, and return (parent) pointers. This structure allows React to:

• Pause diffing mid-tree and yield to the browser for urgent work (input handling, animation frames)
• Resume where it left off without losing progress
• Abort if a higher-priority update arrives

In Concurrent Mode, React assigns priority lanes to updates. User interactions get high priority (synchronous), while data fetching gets lower priority (can be interrupted). The diffing itself is interruptible — this is impossible with the old recursive approach.

Common Anti-Patterns:

• Random keys (key={Math.random()}) — Forces React to unmount/remount on every render, destroying all state and DOM elements.
• Index keys with reorderable lists — React maps by position, not identity, causing state to stick to the wrong element after reordering.
• Unstable component definitions — Defining a component inside another component's render creates a new type on every render, causing the entire subtree to unmount/remount.