Flatten a comment tree for rendering

easyData Structures+150 XPPractice

A virtualised list can only render a flat array, but comment threads and folder trees are nested. The usual fix is to flatten the tree into rows, each carrying the indent level it should be drawn at.

Implement flattenTree(nodes). nodes is an array of root nodes, each shaped { id, children } where children is an array of nodes and may be missing. Return a flat array of objects, each with exactly two properties: id (copied from the node) and depth (a number, 0 for a root). Order the result depth-first in pre-order: a node comes immediately before its own descendants, and siblings keep their array order. An empty input array returns an empty array.

Arguments

nodesArray<{ id: unknown; children?: Node[] }>: An array of root nodes. Each may have a children array.

Returns

Array<{ id: unknown; depth: number }> — A flat list of rows in depth-first pre-order, each carrying the depth at which the node sits.

Examples

flattenTree([
  { id: 1, children: [{ id: 2, children: [{ id: 3 }] }, { id: 4 }] },
]);
// [{ id: 1, depth: 0 }, { id: 2, depth: 1 },
//  { id: 3, depth: 2 }, { id: 4, depth: 1 }]

flattenTree([{ id: "a" }, { id: "b", children: [{ id: "b1" }] }]);
// [{ id: "a", depth: 0 },
//  { id: "b", depth: 0 },
//  { id: "b1", depth: 1 }]

flattenTree([]);
// []

What it has to do

Each entry has exactly two properties, id and depth.
Roots have depth 0 and each level of nesting adds 1.
A node appears immediately before its descendants, and siblings keep their order.
Return an empty array for an empty input.
Treat a missing children property as no children.

Notes

O(n) time and O(h) stack space, where h is the deepest branch.
Pre-order is what virtual lists want — a parent renders before its descendants so the collapse arrow sits at the top of its subtree.

Stuck? The javascript course covers everything this challenge needs.

Try it yourself· Edit the code, then press Run

Loading playground...

5 tests · +150 XP

Discussion

No comments yet. Be the first to say something.

All challenges102 / 150