Introduction

Converting a flat parent-child list into a tree is a common task in menus, comment threads, category hierarchies, and organization charts. The most reliable solution is a two-pass algorithm that first creates all nodes in a lookup map and then links each node to its parent.

That approach is both simple and efficient. It runs in linear time and makes it easier to validate bad input such as duplicate IDs, missing parents, or cyclic data.

Define the Input and Output Clearly

A typical input row contains:

• 'id as the node identifier'
• 'parentId as the parent reference or null for a root'
• additional fields such as name

A typical output is either:

• a list of root nodes, each with children
• or one synthetic root node that wraps the forest

Choose the output contract first, because UI code and API consumers need to know whether multiple roots are possible.

A Two-Pass Linear Algorithm

First create the node objects and store them by ID. Then do a second pass that either attaches each node to its parent or puts it into the root list.

1function buildTree(rows) {
2  const byId = new Map();
3  const roots = [];
4
5  for (const row of rows) {
6    if (byId.has(row.id)) {
7      throw new Error(`Duplicate id: ${row.id}`);
8    }
9
10    byId.set(row.id, {
11      id: row.id,
12      parentId: row.parentId ?? null,
13      name: row.name,
14      children: [],
15    });
16  }
17
18  for (const node of byId.values()) {
19    if (node.parentId === null) {
20      roots.push(node);
21      continue;
22    }
23
24    const parent = byId.get(node.parentId);
25    if (!parent) {
26      throw new Error(`Missing parent for node ${node.id}: ${node.parentId}`);
27    }
28
29    parent.children.push(node);
30  }
31
32  return roots;
33}

This is O(n) time and O(n) space, which is much better than repeatedly scanning the whole list to find parents.

Example Data

1const rows = [
2  { id: 1, parentId: null, name: "Root" },
3  { id: 2, parentId: 1, name: "A" },
4  { id: 3, parentId: 1, name: "B" },
5  { id: 4, parentId: 2, name: "A1" },
6];
7
8const tree = buildTree(rows);
9console.log(JSON.stringify(tree, null, 2));

The result is one root with children A and B, and A itself has child A1.

Add Validation for Real Systems

The tree-building algorithm is straightforward, but production input can still be bad.

Important checks include:

• duplicate IDs
• missing parents
• cycles
• nondeterministic child order

Duplicate IDs and missing parents are easy to catch during the two-pass build. Cycles require an extra traversal if your upstream data is untrusted.

1function assertAcyclic(roots) {
2  const state = new Map();
3
4  function dfs(node) {
5    const s = state.get(node.id) ?? 0;
6    if (s === 1) throw new Error(`Cycle detected at node ${node.id}`);
7    if (s === 2) return;
8
9    state.set(node.id, 1);
10    for (const child of node.children) dfs(child);
11    state.set(node.id, 2);
12  }
13
14  for (const root of roots) dfs(root);
15}

Stable Ordering Matters

If the tree is rendered in a UI, child order should usually be deterministic.

1function sortTree(nodes) {
2  for (const node of nodes) {
3    node.children.sort((a, b) => a.name.localeCompare(b.name));
4    sortTree(node.children);
5  }
6}

Stable ordering helps with caching, snapshot tests, and predictable user experience.

Common Pitfalls

A common mistake is using nested loops to search for each parent repeatedly. That works on tiny datasets and then becomes unnecessarily slow on large ones.

Another issue is silently skipping nodes whose parents are missing. That may hide data-quality problems that should fail loudly.

Developers also often forget cycle detection because the input “should be a tree.” If upstream guarantees are weak, that assumption is dangerous.

Finally, decide what should happen when there are multiple roots. A tree API that assumes a single root but receives a forest will create confusion unless that possibility is handled explicitly.

Summary

• Use a two-pass map-based algorithm to convert flat parent-child rows into a tree efficiently.
• Validate duplicate IDs and missing parents during construction.
• Add cycle detection if input quality is not guaranteed.
• Sort children when deterministic rendering matters.
• Define clearly whether the output is a single root or a list of roots.