The Reconciliation Diffing Algorithm & Heuristics
React uses an O(n) heuristic diffing algorithm based on two assumptions: two elements of different types produce completely different trees, and the developer can hint which child elements are stable across renders with a key prop.
Key Learning Objectives
Explain why general tree comparison algorithms are O(n^3) and how React achieves O(n).
Analyze the element type heuristic: changing <div> to <span> destroys and remounts the entire subtree.
Analyze the same-type heuristic: preserving DOM nodes and only updating changed attributes.
Predict whether component state is preserved or wiped out across render passes.
The Interview Problem & Context
What is logged to the console when comparing state preservation between different element types, same element types with different keys, and identical element types?
1// Simulating React tree comparison heuristics2function simulateReconciliation() {3 const results: string[] = [];45 // 1. Different element types: <div> -> <section> destroys & remounts6 const changeType = 'remount';7 results.push(changeType);89 // 2. Same element type, same position, no key change: preserves state!10 const sameTypeSameKey = 'keep-state';11 results.push(sameTypeSameKey);1213 // 3. Same element type, attribute changed (className): recycles DOM node14 const attrChange = 'recycle';15 results.push(attrChange);1617 return results.join(' ');18}1920console.log(simulateReconciliation());
Predict Console & Render Output
remount keep-state recycle
recycle keep-state remount
remount remount recycle
keep-state recycle remount
Execution Trace
Step 1 of 4 (Line 6)Different element types tear down old Fiber tree and mount fresh tree.
Deep Architectural Explanation
The Reconciliation Diffing Heuristics
Finding the minimum number of operations to transform one arbitrary tree into another has a known complexity of $O(n^3)$ (Levenshtein distance for trees). For 1,000 elements, that is 1 billion operations per frame!
React implements a practical $O(n)$ heuristic algorithm based on two core assumptions:
1. Elements of Different Types Produce Different Trees
Whenever the root elements have different types:
// Before:
<div><Counter /></div>
// After:
<span><Counter /></span>- React does not attempt to match the
<Counter />instances. - It destroys the entire
<div>subtree (unmounting all children and wiping their state) and builds the<span>tree from scratch.
2. Same Element Types Are Mutated in Place
When comparing two React DOM elements of the same type:
// Before:
<div className="before" title="stuff" />
// After:
<div className="after" title="stuff" />- React looks at the attributes of both, keeps the same underlying DOM node, and only mutates
className!
3. Keys Guide Child Element Reordering
Without keys, inserting an item at the beginning of a list forces React to mutate every child. With keys, React uses a map lookup to match existing Fibers and simply moves the DOM nodes.
Common Interview Traps & Pitfalls
Believing React performs an exhaustive mathematical diff of every tree node.
Changing root element tags (div -> section) and wondering why child component state vanished.
Using unstable keys (Math.random()) which forces React to treat every render as a full unmount and remount.
Senior Interviewer Follow-Up Probes
Why does React compare elements level-by-level (breadth-first) rather than depth-first?
How does the new React Compiler affect reconciliation diffing performance?
What happens when two components have the same type but different positions in the tree?
Frequently Asked Interview Questions
What happens when an element's type changes from <div> to <p>?
React destroys the entire old DOM node and all its children, running unmount cleanups and mounting a completely new tree with reset state.
How does React optimize diffing for elements of the same type?
It preserves the underlying DOM node and only updates the specific attributes, styles, or event listeners that changed between render passes.
Why does React not move subtrees across different parents?
React's heuristic algorithm only diffs children at the same level of the tree. If a child moves to a different parent, React remounts it rather than tracking the move.
What role do keys play in the reconciliation algorithm?
Keys provide stable identity across renders, allowing React to match children in lists even when they are inserted, deleted, or reordered.