Build a tree from a flat parent list

Comment threads, category menus and file trees all come out of a database flat: each row carries its own id and its parent's id. The UI needs them nested.

Implement buildTree(rows). Each row is an object with an id and a parentId, and may carry any other fields. Return an array of root nodes. Each node is a new object holding a copy of its row's own properties plus a children array of its child nodes, which is empty for a leaf. Children appear in the order their rows appear in the input, and so do the roots. A row is a root when its parentId is null, or when no row in the input has that id — an orphan is promoted to a root rather than dropped. Rows may appear in any order, so a child may come before its parent. The input rows must not be modified: no children property is ever added to them. An empty input returns an empty array.

What it has to do

• Return an array of root nodes, each a new object with the row's fields plus children.
• Give every node a children array, empty when it has no children.
• Order children and roots by the order their rows appear in the input.
• Treat a row whose parentId is null or refers to no known id as a root.
• Accept rows in any order, and never add children to the input rows.

Your workspace