Flat List to Tree
Given a flat list of { id, name, parentId }, write buildTree(items) returning the roots of a tree.
Every node carries a children array. parentId is null for a root. Roots come back in the order they appeared. A child may be listed before its parent.
Examples
buildTree([
{ id: 1, name: 'Parent', parentId: null },
{ id: 2, name: 'Child', parentId: 1 },
]);[{ id: 1, name: 'Parent', parentId: null,
children: [{ id: 2, name: 'Child', parentId: 1, children: [] }] }]Constraints
- 0 <= items.length <= 10^4
- ids are unique
Notes
- Build the id lookup first and link second, so ordering in the input does not matter.
- Spread each item into a new node rather than mutating the caller’s objects.
Hints
Flat List to Tree (reference solution)
One way to do it. The Editorial tab walks through why it is written this way.
Solution
1function buildTree(items) {
2 const byId = new Map();
3 items.forEach((item) => byId.set(item.id, { ...item, children: [] }));
4 const roots = [];
5 items.forEach((item) => {
6 const node = byId.get(item.id);
7 const parent = item.parentId === null ? undefined : byId.get(item.parentId);
8 if (parent) parent.children.push(node);
9 else roots.push(node);
10 });
11 return roots;
12}Editorial: Flat List to Tree
Two passes, or one and a map
APIs return flat rows because that is what a database returns. UIs need trees. This conversion sits behind every file explorer, comment thread and nested menu.
Approach
Build the lookup first, link second.
Implementation
function buildTree(items) { const byId = new Map(); items.forEach((item) => byId.set(item.id, { ...item, children: [] })); const roots = []; items.forEach((item) => { const node = byId.get(item.id); const parent = item.parentId === null ? undefined : byId.get(item.parentId); if (parent) parent.children.push(node); else roots.push(node); }); return roots; }
Worth knowing
Doing it in two passes is what makes the input order irrelevant — a child listed before its parent still finds it, because every node exists in the map before any linking starts. A single pass that links as it goes has to handle the forward reference some other way.
Spreading each item into a new node rather than adding children to the caller's objects keeps the input clean, which matters when the same data feeds something else. Nodes whose parent is missing entirely are treated as roots rather than dropped, so nothing disappears silently.