React reconciles two element trees in roughly O(n) instead of using a general tree-diff algorithm, which costs about O(n^3). Which assumptions buy that speed, and what does React give up in exchange?
answer
- cubic in the general case
- two assumptions, stated in the docs
- type mismatch ends the search
- identity within one parent's children
- moved subtree is rebuilt, not relocated
basics
~20 sReact assumes different element types produce different trees, and that keys identify stable children. Those bets replace an O(n^3) comparison with one O(n) pass, at the cost of never reusing a subtree that moved to a new parent.
solid answer
~50 sA general algorithm for the minimum edit script between two trees of n nodes is on the order of O(n^3), which is unusable for a UI that re-renders constantly. React replaces it with a single linear walk built on two assumptions. First, two elements of different types produce different trees, so on a type mismatch React stops comparing and rebuilds the subtree rather than hunting for reusable fragments. Second, the developer marks which children are stable across renders with a `key`, so React matches list items by identity instead of searching for a minimal edit script. The tradeoff is real: React only compares nodes that occupy the same position under the same parent, so a subtree moved to a different parent is destroyed and recreated even though an identical one exists elsewhere in the tree.
go deeper
Recall that React compares its own previous element tree with the new one in a single pass, and that a change of element type means rebuild rather than patch.
Name both assumptions and connect each to the cost it removes: the type rule eliminates the search for reusable fragments, and per-parent child identity keeps the children pass linear.
Demonstrate the consequences in real code — a subtree that changes parents is destroyed, an inserted wrapper remounts everything below it — and use that to argue how a tree should be shaped when state must survive.
Own the framing that a framework's update algorithm is an engineering tradeoff, not a truth: React chose predictable linear cost with explainable failure modes, and any team convention about tree structure is really about staying inside those assumptions.
## The problem being avoided Comparing two arbitrary trees and producing the minimum sequence of edits that turns one into the other is a classic algorithm, and the well-known solutions run on the order of O(n^3) in the number of nodes. For a page with a few thousand elements, that is billions of operations for one update — and React does this on every state change, sometimes many times per second. Any algorithm whose cost grows faster than the size of the tree is disqualified before you start. So React does not solve the general problem. It solves a restricted one, in a single pass proportional to the number of elements, by making assumptions about how UI code is actually written. ## Assumption one: different types produce different trees When the element type at a position changes, React does not look inside for anything worth keeping. It unmounts the old subtree and mounts the new one. This is the assumption that eliminates the search: without it, every mismatch would require asking "is any part of the old subtree reusable somewhere in the new one?", which is exactly the expensive question. The assumption is a bet on developer intent. If a slot held a `<Chart>` and now holds a `<Table>`, they almost certainly share no state worth transplanting. The bet is wrong occasionally — a wrapper tag swapped from `div` to `section` throws away state below it that nobody meant to lose — and that cost is accepted deliberately. ## Assumption two: children can be identified Within one parent, React walks the previous and next children together. Position alone is a poor identity for a list whose items get inserted, removed or reordered, so React lets the element carry a `key` that identifies it among its siblings. With keys the match is a lookup rather than a search, which keeps the children pass linear too. ## What linear-time really constrains The practical consequences follow directly from "one pass, comparing like positions": - **No cross-parent reuse.** Moving a subtree to a different parent in the new tree is not detected as a move. The old one unmounts, the new one mounts, and all the state and DOM inside it is recreated. ```jsx // Player is remounted, not moved, when isFullscreen flips return isFullscreen ? <Overlay><Player src={src} /></Overlay> : <Sidebar><Player src={src} /></Sidebar>; ``` - **No level-skipping.** React compares a parent against a parent and its children against its children. Inserting a wrapper around an existing subtree shifts everything below to a new depth, so it all remounts. - **Only siblings are matched against each other.** Keys are scoped to one parent's child list; an identical key elsewhere in the tree means nothing. - **The comparison is over React's own element objects, not the DOM.** React never reads the document to work out what changed; it compares the description it produced last time against the one it just produced, then applies the resulting mutations. ## Why the heuristic holds up UI trees are not arbitrary graphs. They are generated by code whose structure is largely stable between renders: the same components in the same order, with data flowing through props. What actually changes on a typical update is a handful of props and the membership of a list or two. React's algorithm is tuned for exactly that shape, and its worst cases — restructuring the tree wholesale — happen rarely and are visible in the code that causes them. ## How to talk about it A strong answer names the exponent it is avoiding, states both assumptions, and then gives one concrete price paid: a subtree that changes parents is rebuilt from scratch. That last point is what separates someone who has read the sentence from someone who has debugged the consequence. It also helps to say what is *not* claimed. React does not promise the minimum number of DOM operations. It promises a fast, predictable approximation whose failure modes are explainable from the code, which for an interactive UI is worth more than optimality.
- Does React's algorithm produce the minimum number of DOM mutations?No, and it never claims to. It produces a good approximation in linear time. A move across parents, or a wrapper inserted around an existing subtree, causes a full rebuild that an optimal edit script would have avoided. The tradeoff is deliberate: predictable linear cost beats an optimal but unaffordable comparison.
- If React never reads the DOM to diff, how does it know what the document currently looks like?It does not need to. React keeps the element tree it produced on the previous render and compares the new one against that. The DOM is treated as a write target that only React mutates, so its own record is authoritative — which is also why direct external DOM edits inside React-managed nodes are unsafe.
- Where does the linear walk actually spend its time on a large update?Calling component functions and comparing props for every position that is visited. Rendering is not free just because the algorithm is linear — a linear pass over ten thousand elements still runs ten thousand comparisons and re-invokes every component whose subtree is entered.
saying these in an interview costs you the question
- Says React diffs the real DOM against a virtual copy
- Claims React finds the minimal set of DOM edits
- Thinks React detects a node moved between different parents
- Believes the virtual DOM is faster than direct DOM updates
- States O(n) without naming any assumption behind it