Build a tree from a flat list

Before you start

What's tree traversal?

A tree is data shaped like a family tree: one node at the top, the root, and each node may have children, which may have children of their own. A node with no children is a leaf. The DOM is a tree: the document sits at the root, <html> is its child element, and every element's children are the nodes directly inside it. Traversing a tree means visiting every node once, for example to collect the ones that pass a test or to count them.

There are two main orders. Depth-first goes as deep as it can down one branch, all the way to its leaves, before it moves on to the next sibling. Breadth-first goes level by level: the root, then all of its children, then all of their children. In a family tree, depth-first follows one family line down to the youngest generation before turning to the next sibling's line; breadth-first meets everyone generation by generation.

Here's a small part of a page, drawn as a tree, with each element's depth, its distance from <main>:

// <main><article><h2>Title</h2><p>Text</p></article><aside><ul><li>Link</li></ul></aside></main>
//
// main          depth 0
// ├─ article    depth 1
// │  ├─ h2      depth 2
// │  └─ p       depth 2
// └─ aside      depth 1
//    └─ ul      depth 2
//       └─ li   depth 3

Step	Depth-first visits	Breadth-first visits
1	`main`	`main`
2	`article`	`article`
3	`h2`	`aside`
4	`p`	`h2`
5	`aside`	`p`
6	`ul`	`ul`
7	`li`	`li`

Both visit all seven elements; only the order differs. Depth-first finishes article and everything in it before it touches aside. Breadth-first sees both elements at depth 1 before anything at depth 2, so it reaches the nodes nearest the root first.

Depth-first comes in two common variants. Pre-order visits a node before its children, as in the table: that's the order of the start tags in the HTML, which the DOM calls document order. Post-order visits a node after its children: h2, p, article, li, ul, aside, main, the order of the end tags. You meet traversal wherever data nests: the DOM, nested comments and menus, folders and files, and the syntax trees that tools such as Babel and ESLint walk through.

Before you start

What do O(1) and O(n) mean?

Big O notation describes how much more work an operation does as the data grows. It ignores the exact time, which depends on the machine, and keeps only the shape of the growth. n stands for the size of the data: the number of entries, items, or characters.

Notation	Name	As the data grows, the work	Examples
`O(1)`	Constant	Stays the same, whether there are 10 entries or 10 million.	`map.get(key)`, `array[i]`, `array.push(x)`
`O(log n)`	Logarithmic	Grows by one step each time the data doubles.	Binary search in a sorted array
`O(n)`	Linear	Grows in step: twice the data, twice the work.	`array.includes(x)`, `array.shift()`, one loop over everything
`O(n log n)`	Linearithmic	Grows a little faster than the data.	`array.sort()`
`O(n²)`	Quadratic	Grows with the square: twice the data, four times the work.	A loop over an array inside another loop over it

So when a question asks for O(1) operations, it means they must not visit the entries one by one: no indexOf, no includes, no filter, and no shift() or splice() on an array, which move every element after the one removed. Looking a key up in a Map or an object is fine; it's O(1) on average.

Memory is described the same way: O(n) space means the memory used grows in step with the input.

Write arrayToTree(items). Each item is an object with an id and a parentId, like rows from a database or the comments in a thread, and every id is unique. It returns the tree they describe, as an array of root nodes.

A node is a new object with all of the item's own properties, plus children: an array of its child nodes. Every node has children, and a leaf's is empty.

An item is a root when its parentId is null or undefined, or when no item has that id. An item whose parent is missing is kept at the top instead of being lost.

The roots, and the children of each node, keep the order they had in items, and a child may come before its parent. Ids are compared the way a Set compares values, so 1 and "1" are different ids.

If some items form a cycle, such as an item that is its own parent or two items that are each other's parent, no root leads to them. Detect that and throw an Error (new Error(message)), instead of looping or recursing forever. Don't change items or the objects in it.

Build the tree in O(n) time. The tests check this by counting how often your code reads id and parentId on a list of 500 items: at most 50 reads per item, so searching the whole list again for each item fails.

const comments = [
  { id: 1, parentId: null, text: "First!" },
  { id: 2, parentId: 1, text: "Reply" },
  { id: 3, parentId: 2, text: "Reply to the reply" },
  { id: 4, parentId: null, text: "Another thread" },
];
 
arrayToTree(comments);
// [
//   { id: 1, parentId: null, text: "First!", children: [
//     { id: 2, parentId: 1, text: "Reply", children: [
//       { id: 3, parentId: 2, text: "Reply to the reply", children: [] },
//     ] },
//   ] },
//   { id: 4, parentId: null, text: "Another thread", children: [] },
// ]
 
arrayToTree([{ id: 1, parentId: 2 }, { id: 2, parentId: 1 }]); // throws an Error

What the tests check

builds the tree from parent ids

const comments = [
  { id: 1, parentId: null, text: "First!" },
  { id: 2, parentId: 1, text: "Reply" },
  { id: 3, parentId: 2, text: "Reply to the reply" },
  { id: 4, parentId: null, text: "Another thread" },
];
expect(arrayToTree(comments)).toEqual([
  {
    id: 1,
    parentId: null,
    text: "First!",
    children: [{ id: 2, parentId: 1, text: "Reply", children: [{ id: 3, parentId: 2, text: "Reply to the reply", children: [] }] }],
  },
  { id: 4, parentId: null, text: "Another thread", children: [] },
]);

makes items with a null or missing parentId roots, in order

const tree = arrayToTree([{ id: "b" }, { id: "a", parentId: null }, { id: "c", parentId: "a" }]);
expect(tree.map((node) => node.id)).toEqual(["b", "a"]);
expect(tree[1].children.map((node) => node.id)).toEqual(["c"]);

keeps children in their original order, even before their parent

const tree = arrayToTree([
  { id: 3, parentId: 1 },
  { id: 2, parentId: 1 },
  { id: 1, parentId: null },
  { id: 5, parentId: 4 },
  { id: 4, parentId: 1 },
]);
expect(tree.map((node) => node.id)).toEqual([1]);
expect(tree[0].children.map((node) => node.id)).toEqual([3, 2, 4]);
expect(tree[0].children[2].children.map((node) => node.id)).toEqual([5]);

gives every node a children array, empty for leaves

const tree = arrayToTree([{ id: 1, parentId: null }, { id: 2, parentId: 1 }]);
expect(Array.isArray(tree[0].children)).toBe(true);
expect(tree[0].children[0].children).toEqual([]);
expect(arrayToTree([])).toEqual([]);

puts items whose parent is missing at the top

const tree = arrayToTree([
  { id: 1, parentId: null },
  { id: 2, parentId: 99 },
  { id: 3, parentId: 2 },
]);
expect(tree.map((node) => node.id)).toEqual([1, 2]);
expect(tree[1].children.map((node) => node.id)).toEqual([3]);

compares ids the way a Set does

const tree = arrayToTree([
  { id: 1, parentId: null },
  { id: "1", parentId: null },
  { id: 2, parentId: "1" },
]);
expect(tree.map((node) => node.id)).toEqual([1, "1"]);
expect(tree[0].children).toEqual([]);
expect(tree[1].children.map((node) => node.id)).toEqual([2]);

throws an Error when items form a cycle

const lists = [
  [{ id: 1, parentId: 1 }],
  [{ id: 1, parentId: 2 }, { id: 2, parentId: 1 }],
  [{ id: 1, parentId: null }, { id: 2, parentId: 3 }, { id: 3, parentId: 2 }, { id: 4, parentId: 2 }],
];
for (const items of lists) {
  let thrown;
  try {
    arrayToTree(items);
  } catch (error) {
    thrown = error;
  }
  // A stack overflow, or a loop the page stops after a second, throws a different kind of error: report it here.
  expect(thrown).toBeInstanceOf(Error);
  if (thrown.name !== "Error") throw new Error("Expected an Error, but got " + thrown.name + ": " + thrown.message);
}

copies the items instead of changing them

const items = [{ id: 1, parentId: null, label: "root" }, { id: 2, parentId: 1 }];
const tree = arrayToTree(items);
expect(tree[0]).not.toBe(items[0]);
expect(tree[0].label).toBe("root");
expect(items[0]).toEqual({ id: 1, parentId: null, label: "root" });
expect(items[1]).toEqual({ id: 2, parentId: 1 });
expect(items).toHaveLength(2);

reads id and parentId at most 50 times per item, on 500 items

// A balanced tree of 500 items, children listed first. Every read of an item's id or parentId is counted.
let reads = 0;
const counted = (value) => {
  reads++;
  if (reads > 25000) throw new Error("Stopped after 25,000 reads of id and parentId, 50 per item: the code searches the list again for each item");
  return value;
};
const items = Array.from({ length: 500 }, (_, i) => ({
  get id() {
    return counted(i);
  },
  get parentId() {
    return counted(i === 0 ? null : Math.floor((i - 1) / 2));
  },
})).reverse();
const tree = arrayToTree(items);
expect(reads).toBeLessThanOrEqual(25000);
expect(tree).toHaveLength(1);
expect(tree[0].id).toBe(0);
expect(tree[0].children.map((node) => node.id)).toEqual([2, 1]);
let count = 0;
const stack = [...tree];
while (stack.length > 0) {
  const node = stack.pop();
  count++;
  stack.push(...node.children);
}
expect(count).toBe(500);

Learn more

solution.jsSaved in this browser

Run tests runs every test on your code, here in your browser. The problem is solved when they all pass.

Ctrl + Enter runs the tests (⌘ + Enter on a Mac).

Build a tree from a flat list

What's tree traversal?

What do O(1) and O(n) mean?

What the tests check

Learn more

Tuto

Hi, I'm Tuto

Give feedback