Describe React's diffing algorithm and its O(n) heuristics

WHAT THIS TESTS: This question tests whether you understand the reconciliation algorithm at a conceptual level, specifically why React rejects the theoretically optimal minimum-edit-distance approach in favor of heuristic assumptions that yield linear time complexity. Interviewers want to see that you grasp the practical trade-offs between algorithmic correctness and runtime performance in a UI library, and that you can explain how component identity and state preservation depend on these rules.

A GOOD ANSWER COVERS: A strong answer hits four things in order. First, state the motivation: generating the minimum number of operations to transform one tree into another is an O(n³) problem, which means one thousand elements could require roughly one billion comparisons, so React opts for a heuristic O(n) algorithm. Second, describe the first heuristic: whenever root elements have different types, React tears down the entire old tree, destroys old DOM nodes, calls componentWillUnmount, and builds a new tree from scratch, inserting new nodes and calling componentDidMount; this means any state below the root is lost. Third, describe the same-type path: when elements share the same type, React keeps the underlying DOM node and only updates changed attributes, such as modifying a single className or a specific style property like color while leaving fontWeight untouched, then it recurses on children. Fourth, explain the second heuristic: by default React iterates over both child lists simultaneously and generates mutations on difference, which is inefficient for insertions at the beginning; the key prop lets developers hint which child elements are stable across renders so React can match moved children by identity rather than position.

COMMON WRONG ANSWERS: Candidates often claim the diff is O(n) because of the virtual DOM itself, confusing the diffing algorithm with the act of creating a lightweight JavaScript representation. Another red flag is saying keys are only for performance or list rendering; keys are an identity hint that tells React which component instance corresponds to which element across renders, directly affecting whether state is preserved or destroyed. Some candidates also forget that different types at the root cause a full teardown of everything below, incorrectly suggesting React might diff across type boundaries.

LIKELY FOLLOW-UPS: An interviewer might ask what happens to component state when a parent element type changes, expecting you to say all state below is lost. They might ask for a concrete example where missing keys causes a bug, such as an uncontrolled input retaining stale values when list order changes. They could also ask how React handles children when keys are omitted and an item is inserted at the beginning of a list, expecting you to describe the simultaneous iteration and mutation behavior.

ONE CONCRETE EXAMPLE: Imagine a list rendered as a ul containing three li items. If you insert a new item at the beginning without keys, React iterates position by position, sees mismatches at every index, and mutates every existing node to show the wrong content before finally inserting a new node at the end, effectively destroying and recreating the DOM for every child. If you instead assign stable keys, React recognizes the existing li elements by identity, inserts only the new first node, and leaves the others untouched, preserving any focus or state inside them.