Reconciliation

Reconciliation is the algorithm React uses to diff one tree of React Elements against another to determine the minimum number of operations required to update the UI.

When a component’s state or props update, React generates a new Virtual DOM tree. React then needs to figure out how to efficiently update the previous Virtual DOM tree to match the new one.

Calculating the difference between two arbitrary trees has an algorithmic complexity in the order of O(n³). If React used this standard algorithm, displaying 1000 elements would require one billion comparisons.

React’s Heuristic O(n) Algorithm

React implements a heuristic O(n) algorithm based on two assumptions:

Two elements of different types will produce different trees.
The developer can hint at which child elements may be stable across different renders with a key prop.

1. Elements of Different Types

Whenever the root elements of two trees have different types, React will tear down the old tree and build the new tree from scratch.

For example, changing a <div> to a <span>, or an <Article> to a <Comment>:

// Old Tree
<div>
  <Counter />
</div>

// New Tree
<span>
  <Counter />
</span>

Because the root tag changed from div to span, React destroys the old Counter and mounts a completely new one. Its state is lost.

2. DOM Elements of the Same Type

When comparing two React DOM elements of the same type, React looks at the attributes, keeps the same underlying DOM node, and only updates the changed attributes.

<div className="before" title="stuff" />

<div className="after" title="stuff" />

By comparing these two elements, React knows to only modify the className on the underlying DOM node, leaving the title intact.

3. Component Elements of the Same Type

When a component updates, the instance stays the same, so that state is maintained across renders. React updates the props of the underlying component instance to match the new element, and calls the component’s render function. The diffing algorithm then recurses on the previous result and the new result.

4. Recursing on Children (Keys)

When React diffs a list of children, it iterates over both lists at the same time and generates a mutation whenever there’s a difference.

If you add an element to the end of a list, it performs well:

<ul>
  <li>first</li>
  <li>second</li>
</ul>
// ... changes to ...
<ul>
  <li>first</li>
  <li>second</li>
  <li>third</li>
</ul>

But if you add an element to the beginning, React would normally mutate every single child, which is highly inefficient. This is why React requires keys. When children have keys, React uses the key to match children in the original tree with children in the subsequent tree, easily identifying insertions, deletions, and reorders.

Interview Questions

Q: What is the Reconciliation algorithm?
A: It is the “diffing” process React uses to update the UI efficiently. React creates a new Virtual DOM tree representing the new state, and compares it against the previous Virtual DOM tree. It calculates the absolute minimum number of real DOM mutations needed to bring the screen into alignment with the new state, and then applies them all at once.