跪拜 Guibai
← Back to the summary

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

Foreword

Anyone who has written an admin dashboard has probably encountered this task:

The backend throws over a flat array, and the frontend needs to render it as a multi-level menu tree.

Address cascades, organizational charts, product category trees… Any feature involving "hierarchy" almost always boils down to the same pattern: listToTree.

This article breaks down two mainstream approaches and discusses their respective characteristics.

1. Why the backend always gives you a flat array

Many newcomers' first reaction is: why doesn't the backend just give me a tree? Giving me a one-dimensional array seems so unprofessional.

It's really not that the backend is lazy. It's because MySQL's table structure itself is one-dimensional.

Dimension Flat Array Tree Structure
Storage method One row per record, linked by a parentId field Nested objects, children arrays
Database friendliness ✅ Direct select * from ❌ Relational databases are not good at nesting
Transmission size Small Large (parent node info stored redundantly)
Frontend processing Needs to be converted to a tree Ready to use
Real-world projects Backend returns Frontend assembles

So the industry convention is: database stores flat, API returns flat, frontend converts to tree. The parentId field is the bridge between flat and tree structures.

2. First, look at the raw data

js

const flatList = [
    { id: 1, name: 'First-level Menu A', parentId: 0 },
    { id: 2, name: 'First-level Menu B', parentId: 0 },
    { id: 3, name: 'Second-level A-1', parentId: 1 },
    { id: 4, name: 'Third-level A-1-1', parentId: 3 },
    { id: 5, name: 'Second-level B-1', parentId: 2 }
]

Two key conventions:

  1. id is the node's unique identifier
  2. parentId points to the parent node's id; parentId: 0 usually means "no parent node", i.e., a root node

Some projects use parentId: null or parentId: -1 to indicate a root node. The convention differs, but the approach is the same.

3. The brute-force O(n²) approach: don't learn it, just know how bad it is

The most intuitive approach is: for each node, loop through the entire array again to find its parent node.

js

// Pseudocode, don't write this in production
list.forEach(item => {
    const parent = list.find(n => n.id === item.parentId);
    if (parent) parent.children.push(item);
    else tree.push(item);
});

It works, but finding the parent for each node is O(n), and with n nodes, it's O(n²).

For 100 menu items, it doesn't matter. At 1000 items, it starts to lag. At 10000 items, the screen goes white.

Approach Time Complexity Space Complexity Verdict
Brute-force double loop O(n²) O(n) Entry-level, don't use it
Hash table, two-pass O(n) O(n) Production standard

4. The core idea of O(n) optimization: enter the hash table

Where is the brute-force method slow? The step of finding the parent node is O(n).

If the parent node could be retrieved in O(1), the overall complexity drops to O(n).

What data structure offers O(1) lookup? A hash table. In JS, that's Map or a plain object {}.

Two steps:

  1. First pass: Put every node into a Map, with the key being the id and the value being the node itself (with an empty children array).
  2. Second pass: For each node, use parentId to retrieve the parent node from the Map in O(1), and push itself into the parent's children array; if no parent node is found (root node), push it into the tree array.

5. Code 1: Map + forEach approach

js

function listToTree(list) {
    const map = new Map();       // ES6 HashMap data structure
    const tree = [];

    // First pass: build Map, each node gets a children array
    list.forEach((item) => {
        map.set(item.id, {
            ...item,             // Spread existing fields
            children: []         // Reserve children array
        });
    });

    // Second pass: mount based on parentId
    list.forEach(item => {
        const current = map.get(item.id);        // Current node
        const parent = map.get(item.parentId);   // Its parent node
        if (parent) {
            parent.children.push(current);       // Mount to parent
        } else {
            tree.push(current);                  // No parent → root node
        }
    });

    return tree;
}

Line-by-line breakdown:

Line Purpose Why it's written this way
new Map() Create hash table Map lookup is O(1)
...item Spread original fields Doesn't mutate original data, shallow copy
children: [] Reserve child array Needs to be pushable later, must be an empty array
map.get(item.parentId) O(1) parent lookup The soul of the hash table
if (parent) check Distinguish root/child When parentId is 0, get returns undefined

Note: Map.get(0) returns undefined in our data (because there is no node with id 0), so root nodes enter the else branch and are pushed to tree.

6. Code 2: reduce approach

Same logic, different style:

js

function listToTree(list) {
    // First pass: build map with reduce
    const nodeMap = list.reduce((map, item) => {
        map[item.id] = { ...item, children: [] };
        return map;
    }, {});

    // Second pass: assemble tree with reduce
    return list.reduce((tree, item) => {
        const cur = nodeMap[item.id];
        const parent = nodeMap[item.parentId];
        if (parent) {
            parent.children.push(cur);
        } else {
            tree.push(cur);
        }
        return tree;
    }, []);
}

Differences from Code 1:

Comparison Item Code 1 Code 2
Hash table new Map() Plain object {}
Iteration method forEach reduce
Key access map.get(id) / map.set(id, v) map[id] / map[id] = v
Style Imperative, clear step-by-step Functional, more compact chaining
Readability High, beginner-friendly Medium, requires understanding reduce

Both approaches have identical logic, and performance is basically the same. It's purely a matter of style.

7. Map vs Plain Object: which hash table to use?

This is a common interview question, and the first choice to make when writing listToTree.

Dimension Map Plain Object {}
Key type Any (including objects, numbers) Only strings/Symbols
Iteration order Insertion order Integer keys sorted first
Size retrieval map.size Object.keys(obj).length
Performance Slightly better for frequent add/delete Slightly better for static access
Prototype pollution ❌ No ⚠️ Possible (__proto__, etc.)
Serialization ❌ No JSON support ✅ JSON.stringify

In a listToTree scenario, ids are usually numbers, so either works. But using Map is more "modern" and safer (no fear of keys like __proto__). Map is recommended for production code.

8. forEach vs reduce: a battle of styles

Dimension forEach reduce
Return value undefined Accumulator (any type)
Side effects Mutates external variables Hides state inside the accumulator
Readability Straightforward, like a for loop Functional, a bit mind-bending
Suitable for Multi-step processes, pure iteration Accumulation, reduction, building tables
Chainable ❌ ✅ Can chain .filter().map()

I personally prefer the forEach approach, because listToTree is a "two-step" imperative process, and forEach is more straightforward. The reduce version suits teams that prefer a functional style.

9. Complexity analysis

Metric Complexity Explanation
Time O(n) Two passes, each O(n), constant factor 2
Space O(n) Map stores all nodes; tree also stores all nodes

Compared to the brute-force O(n²), when n = 10000, O(n) is roughly 10000 times faster. That's the power of the hash table.

10. Warnings

Pitfall 1: parentId has no root node identifier

If parentId is null instead of 0 in the data, map.get(null) also returns undefined, and the logic works. But if a record's parentId points to a non-existent id, that record will be mistakenly treated as a root node. Add validation in production.

Pitfall 2: Reference issues

In the second pass, what's pushed into children is not a copy, but the same reference from the Map. So nodes in tree and map are the same objects; changing one changes both. This is usually what we want, but be aware of it.

Pitfall 3: Order dependency

If a parent node appears after its child node (parentId points to an id that appears later), the two-pass method still works correctly—because the first pass puts all nodes into the Map first, and the second pass does the mounting. This is also why "two-pass traversal" is more robust than "single-pass recursive mounting".

Pitfall 4: Root node judgment condition

The if (parent) check relies on parentId: 0 not being found in the Map. If you use parentId: null, the behavior is the same; but if someone carelessly writes a node with id: 0, the root node judgment breaks. Clarify the convention before coding.