#Objects#Trees

Flat List to Tree

Turn a flat array of nodes with parentId into a nested tree — the shape behind every file explorer and nested menu.

By Pratik RaiMedium

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

Input:

JSfile.javascript
1buildTree([ 2 { id: 1, name: 'Parent', parentId: null }, 3 { id: 2, name: 'Child', parentId: 1 }, 4]);

Output:

[{ id: 1, name: 'Parent', parentId: null,
   children: [{ id: 2, name: 'Child', parentId: 1, children: [] }] }]

The child is nested under the node whose id its parentId names.

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.

How to solve it

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

JSfile.javascript
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}

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.

Goal: Produce the roots of a correctly nested tree in one pass over a lookup.

Frequently asked questions

How do you build a tree from a flat list?
Create a lookup from id to node first, each with an empty children array. Then walk the list again and attach every node to its parent, collecting the ones with no parent as roots.
Why two passes instead of one?
So the order of the input does not matter. Because every node exists in the lookup before any linking begins, a child listed before its parent still finds it.
What should happen to a node whose parent is missing?
Treating it as a root keeps the data visible rather than silently dropping it. Discarding orphans is also defensible, but it should be a decision you state rather than an accident.
Where does this come up in frontend work?
Anywhere an API returns rows and the UI needs nesting: file explorers, comment threads, nested navigation, category pickers and org charts all consume the same transformation.

Related Challenges

Continue learning with these related challenges

View All
JavaScript

Resolve Promises Sequentially

Run promises one after another and collect the results in order — built with .then chaining, no async/await.

JavaScript · ES6 — Pratik Rai ·

JavaScript

Deep Equality

Compare two values structurally, because === only ever compares references.

JavaScript · ES6 — Pratik Rai ·

JavaScript

Deep Clone

Copy a nested structure so nothing is shared — including the cases that break a naive recursion.

JavaScript · ES6 — Pratik Rai ·