Array to Tree Algorithm

Managing data almost always involves working with hierarchical or nested data. Whether we are talking about nested files and folders, product categories and sub-categories, music, ... you name it. But we store data in a database in a flat structure. This makes sense because the data objects themselves share the same attributes and it makes for easy searching. But how we store the data and how we need to visualize and manipulate it don't necessarily match. So how do we efficiently transform a flat array to a tree? Day 5 of 30 Days of Algorithms will present one solution with O(n) complexity.

Array to Tree Step-by-step

We start by creating a variable for the root item (item without a parentId), and a lookup table for all of the other items.

Items are added to the lookup by their parentId. We only need a placeholder to begin with. As we look through each item, if its ID is in the lookup, we will add its details when we encounter it.

Look for the current item in the lookup. If we find it, add its details.

Create a variable/symbol for the current item.

Determine where the item goes in the tree. If it has no parentId, it is a root note. If it has a parentId, it is a child of some element, we just don't know which one at this point.

Add the placeholder for the parent of the current item. Note that this is not the same as Step 2 where we added a placeholder for the the item.

Add the current item to its parent.

Step 7 is critical to how the array to tree algorithm works. It leverages a feature of JavaScript in order to to this. In JavaScript, all variables are references, not copies. So when we add the variable for a child to its parent's children array, we are moving its reference to that location, not merely a copy. So our item that was previously set to a spot in the lookup, is now in the children of its parent. We don't end up with 2 copies because of the nature of JavaScript's use of references for all variables.

The JavaScript Code

This code is also available as a gist on my github repository.

/**
 * Unflattens an array to a tree with runtime O(n)
 *
 * This algorithm was taken from Philip Stanislaus's
 * "Performant Array to Tree" which has O(n) complexity.
 * It builds the tree in a single pass.
 * @link https://github.com/philipstanislaus
 * @link https://www.npmjs.com/package/performant-array-to-tree
 */
const arrayToTree = (items) => {
  /**
   * The nested tree.
   * @type {*[]}
   */
  const rootItems = [];

  // (1) Create a holder for each item.

  const lookup = {};

  for (const item of items) {
    const itemId = item["id"];
    const parentId = item["parentId"];

    // (2) Create a placeholder for each item in the lookup.
    // Details are added later.

    if (!lookup[itemId]) lookup[itemId] = { ["children"]: [] };

    // (3) Add the details of the item.

    lookup[itemId] = { ...item, ["children"]: lookup[itemId]["children"] };

    // (4) Create a variable for the current item.

    const TreeItem = lookup[itemId];

    // (5) Determine where the item goes in the tree.

    // If the item has no parentId, it is the root node.
    if (parentId === null || parentId === undefined || parentId === "") {
      rootItems.push(TreeItem);
    } else {
      /*
       * If the item has a parentId, add it to the tree.
       */
      // (6) Add a placeholder for parent of the current item.

      if (!lookup[parentId]) lookup[parentId] = { ["children"]: [] };

      // (7) Add the current item to its parent.

      lookup[parentId]["children"].push(TreeItem);
    }
  }

  return rootItems;
};

const tree = arrayToTree([
  { id: "x001", parentId: null, name: "Joe" },

  { id: "x002", parentId: "x001", name: "Sammy", children: [] },
  { id: "x003", parentId: "x001", name: "Emily", children: [] },
  { id: "x004", parentId: "x001", name: "Scott", children: [] },

  { id: "x005", parentId: "x002", name: "Fred", children: [] },
  { id: "x006", parentId: "x002", name: "Vickie", children: [] },
  { id: "x007", parentId: "x002", name: "Marlow", children: [] },

  { id: "x008", parentId: "x003", name: "Anna", children: [] },
  { id: "x009", parentId: "x003", name: "Brad", children: [] },
  { id: "x010", parentId: "x003", name: "Sarah", children: [] },

  { id: "x011", parentId: "x004", name: "Mark", children: [] },
  { id: "x012", parentId: "x004", name: "Debbie", children: [] },
  { id: "x013", parentId: "x004", name: "Boomer", children: [] },

  { id: "x014", parentId: "x005", name: "Stuey", children: [] },
  { id: "x015", parentId: "x005", name: "Jessie", children: [] },
  { id: "x016", parentId: "x005", name: "Tolstoy", children: [] },

  { id: "x017", parentId: "x009", name: "Maddie", children: [] },
  { id: "x018", parentId: "x009", name: "Scout", children: [] },
  { id: "x019", parentId: "x009", name: "Jordie", children: [] },
]);

console.log(JSON.stringify(tree, undefined, 2));

You can grab the code from my Github repository for the 30 Days of Algorithms series. Feel free to leave feedback or ask questions in the comments below, or reach me via the Contact Page.

Image Credit : Banner image adapted from public domain image by David Eppstein for Wikipedia.