Frontend · JavaScript

listToTree in O(n): Why the Hash Table Beats the Brute-Force Double Loop

By 两只羊ovo · Aug 8, 2026

Read original on juejin.cn ↗ Google Translate ↗ Alt translation

Admin dashboards, category pickers, and org charts all depend on this transformation. A quadratic implementation that works fine on a dozen items will silently degrade into a multi-second freeze on real datasets, and the O(n) hash-table pattern is the standard fix that every frontend developer should reach for by reflex.

Summary

Backend APIs return flat arrays because relational databases store rows, not trees. The frontend must reassemble the hierarchy using a `parentId` field. A naive double loop that searches for each node's parent hits O(n²) and freezes the UI around a thousand records. The fix is a hash table: one pass to index every node by ID, a second pass to attach each node to its parent in O(1). The result is a clean O(n) algorithm that handles tens of thousands of nodes without strain. Two JavaScript implementations — one using `Map` with `forEach`, another using a plain object with `reduce` — achieve the same performance. The `Map` version avoids prototype-pollution edge cases and is the safer production default. Common pitfalls include missing root-node identifiers, shared object references between the map and the output tree, and broken root detection when an `id: 0` node exists.

Takeaways

— Relational databases store flat rows, so backends return flat arrays; the frontend is responsible for building the tree.

— A brute-force nested loop that searches for each node's parent runs in O(n²) and becomes unusable beyond a few hundred records.

— Indexing all nodes in a hash table (Map or plain object) on the first pass enables O(1) parent lookups on the second pass, yielding O(n) overall.

— The `Map`-based implementation avoids prototype-pollution risks (e.g., a key named `__proto__`) and is the safer choice for production.

— Using `reduce` instead of `forEach` produces a more compact, functional-style version with identical performance.

— Shared references between the hash table and the output tree mean mutations propagate both ways, which is usually desired but must be understood.

— Root-node detection via `if (parent)` breaks if the dataset contains a node with `id: 0`, because `Map.get(0)` will find it instead of returning `undefined`.

— Orphan nodes whose `parentId` points to a non-existent ID are silently promoted to root nodes unless explicit validation is added.

Conclusions

The two-pass approach is more robust than a single-pass recursive build because it decouples node registration from parent-child attachment, making it immune to ordering issues where a child appears before its parent in the flat array.

The `Map` vs. plain-object debate in this context is less about performance and more about correctness under adversarial keys; `Map` eliminates an entire class of bugs that most developers never think about until a `__proto__` or `constructor` key appears in production data.

The article's framing of the brute-force method as 'don't learn it, just know how bad it is' is practical pedagogy: it acknowledges the intuitive solution while immediately steering developers toward the production-grade alternative.

Concepts & terms

listToTree

A common frontend algorithm that converts a flat array of nodes (each with an `id` and a `parentId`) into a nested tree structure with `children` arrays, used for menus, category trees, and org charts.

Hash table (Map / plain object) for O(1) lookup

By indexing every node by its `id` in a Map or object, the algorithm can find any parent node in constant time instead of scanning the entire array, reducing the overall complexity from O(n²) to O(n).

Two-pass tree construction

A strategy where the first pass registers all nodes in a lookup table with empty `children` arrays, and the second pass attaches each node to its parent. This avoids ordering dependencies and keeps the logic linear.

Source: juejin.cn ↗ Google Translate ↗ Backup ↗