A simple tree building algorithm5 min read

In this article, I will show you a simple JavaScript algorithm to build a tree, using functional programming.

In my journey of developing Naept, I encountered the need to build trees. An easy example of what is a tree, are the chapters of a document. If the document is the trunk, all the main chapters are the branches of that tree. And all those main chapters may be divided in sub-chapters, which may be, in turn, again sub-divided in sub-sub-chapters, and so on…

Inside the database

The most simple thing to do when storing objects that constitute a tree inside a database, is giving them a link to their parent.

So each one of my chapters has a parent_id property. And if this parent_id‘s value is null for some elements, that means that they are each the root element of a tree.

So from this point, in theory, we should be able to “build a tree”, and what I mean by that is creating a software representation of this tree:

Yes, I know my tree is weird, growing from the left to the right instead of growing up. But you get the idea!

A functional programing approach

I’ve not always been a JavaScript programmer. I’ve actually started very low, abstraction-wise. Like Assembly, C, even VHDL. I’ve been introduced to Object Oriented Languages with C++ more than a decade ago and I’ve loved it. But with JavaScript, I’ve developed an interest for functional programing, and I wanted to solve this problem with functional programing.

So, let’s get back on track.

Each of these Chapter objects potentially has Chapter objects as it’s children (sub-chapters). And each of these children Chapter objects may have children of their own, and so on… While reading this you may see a pattern emerges in your mind. Recursion!

I’ve always loved recursion. It’s one of the beauty of programing. And for once, it’s not an imitation of nature. It is unique to programing. Recursion cannot be found in nature (or perhaps fractals may come close ?).

Anyway, the idea of our algorithm will be to recursively build a tree, sub-tree by sub-tree, using recursion and functional programing.

Let’s code!

First, the chapters. Let’s say we have an array of objects, each object being one chapter :

let chapters = [
  {
    id: 1,
    parent_id: null,
    text: 'Chapter 1',
  },
  {
    id: 2,
    parent_id: null,
    text: 'Chapter 2',
  },
  {
    id: 3,
    parent_id: null,
    text: 'Chapter 3',
  },
  {
    id: 4,
    parent_id: 1,
    text: 'Chapter 1.1',
  },
  {
    id: 5,
    parent_id: 1,
    text: 'Chapter 1.2',
  },
  {
    id: 6,
    parent_id: 1,
    text: 'Chapter 1.3',
  },
  {
    id: 7,
    parent_id: 3,
    text: 'Chapter 3.1',
  },
  {
    id: 8,
    parent_id: 3,
    text: 'Chapter 3.2',
  },
  {
    id: 9,
    parent_id: 5,
    text: 'Chapter 1.2.1',
  },
  {
    id: 10,
    parent_id: 5,
    text: 'Chapter 1.2.2',
  },
  {
    id: 11,
    parent_id: 7,
    text: 'Chapter 3.1.1',
  },
  {
    id: 12,
    parent_id: 7,
    text: 'Chapter 3.1.2',
  },
]

The idea is to get this structure out of the algorithm :

[
  {
    id: 1,
    parent_id: null,
    text: "Chapter 1",
    children: [
      {
        id: 4,
        parent_id: 1,
        text: "Chapter 1.1",
        children: []
      },
      {
        id: 5,
        parent_id: 1,
        text: "Chapter 1.2",
        children: [
          {
            id: 9,
            parent_id: 5,
            text: "Chapter 1.2.1",
            children: []
          },
          {
            id: 10,
            parent_id: 5,
            text: "Chapter 1.2.2",
            children: []
          }
        ]
      },
      {
        id: 6,
        parent_id: 1,
        text: "Chapter 1.3",
        children: []
      }
    ]
  },
  {
    id: 2,
    parent_id: null,
    text: "Chapter 2",
    children: []
  },
  {
    id: 3,
    parent_id: null,
    text: "Chapter 3",
    children: [
      {
        id: 7,
        parent_id: 3,
        text: "Chapter 3.1",
        children: [
          {
            id: 11,
            parent_id: 7,
            text: "Chapter 3.1.1",
            children: []
          },
          {
            id: 12,
            parent_id: 7,
            text: "Chapter 3.1.2",
            children: []
          }
        ]
      },
      {
        id: 8,
        parent_id: 3,
        text: "Chapter 3.2",
        children: []
      }
    ]
  }
]

Each node (chapter) is given a children attribute. This attribute is an array containing the node’s children (sub-chapters).

So what our algorithm will do is, being given the whole array of nodes, and the id of the parent node:

1. filter the array to keep only the nodes with the given parent_id;
2. return an array of those nodes, and in each of them we add a children attribute, which is an array, and this array is build using a function that, being given the whole array of nodes, and the id of the current node as the parent_id argument, will:
   1. filter the array to keep only the nodes with the given parent_id;
   2. return an array of those nodes, and in each of them we add a children attribute, which is an array, and this array is build using a function that, being given the whole array of nodes, and the id of the current node as the parent_id argument , will:
      1. filter the array to keep only the nodes with the given parent_id;
      2. return an array of those nodes, and in each of them we add a children attribute, which is an array, and this array is build using a function that, being given the whole array of nodes, and the id of the current node as the parent_id argument , will:
         • …well, you get the idea…

Here is how it translates into JavaScript:

function makeTree(nodes, parentId) {
  return nodes
    .filter((node) => node.parent_id === parentId)
    .reduce(
      (tree, node) => [
        ...tree,
        {
          ...node,
          children: makeTree(nodes, node.id),
        },
      ],
      [],
    )
}

Using the reduce function, which is emblematic of functional programing, we build the array of nodes of one level, adding the children array to each node and filling it up by calling the makeTree function.

---

Thanks for reading me. I hope you enjoyed this article.

Please comment this article and share your way of building trees, which is probably different.

Have a nice day!