A simple tree building algorithm

Julien Aupart
Sep 7, 2020 · 5 min read

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

Also available in french

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 into 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 programming 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 in functional programming, and I wanted to solve this problem with functional programming.

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 beauties of programming. And for once, it’s not an imitation of nature. It is unique to programming. 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 programming.

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:

  • filter the array to keep only the nodes with the given parent_id;
  • return an array of those nodes, and in each of them we add a children attribute, which is an array, and this array is built using a function that, being given the whole array of nodes, and the id of the current node as the parent_id argument, will:
  • filter the array to keep only the nodes with the given parent_id;
  • 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:
  • filter the array to keep only the nodes with the given parent_id;
  • return an array of those nodes, and in each of them we add a children attribute, which is an array, and this array is built 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 programming, 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. You can read the french version of it on the blog of my company, alongside a lot of other articles on documentation, which is what we do at Naept.

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

Have a nice day!

Originally published at https://www.naept.com on September 7, 2020.

Weekly Webtips

Explore the world of web technologies through a series of tutorials

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store