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.

buildTree([
  { id: 1, parentId: null },
  { id: 2, parentId: 1 },
  { id: 3, parentId: 1 },
]);
// [{ id: 1, parentId: null, children: [
//     { id: 2, parentId: 1, children: [] },
//     { id: 3, parentId: 1, children: [] },
// ] }]

buildTree([
  { id: 1, parentId: null },
  { id: 9, parentId: 404 },
]).map((node) => node.id);
// [1, 9] — an orphan (parentId not in the list) is promoted to a root