Building a hierarchical tree from a flat list — Explained in detail
In this article we are going to explain my answer to a stack-overflow questions, where we build a hierarchical tree; given an array that contains id and parent id, create a hierarchical tree that will parse the data and spit out a formatted object.
Given this array
const list = [
{"Id":"1", "Name":"abc", "Parent":""},
{"Id":"2", "Name":"abc", "Parent":"1"},
{"Id":"3", "Name":"abc", "Parent":"2"},
{"Id":"4", "Name":"abc", "Parent":"2"}
];The output should look like this.
{
"Id": "1",
"Name": "abc",
"Parent": "",
"children": [
{
"Id": "2",
"Name": "abc",
"Parent": "1",
"children": [
{
"Id": "3",
"Name": "abc",
"Parent": "2",
"children": []
},
{
"Id": "4",
"Name": "abc",
"Parent": "2",
"children": []
}
]
}
]
}If you look at the stack-overflow question there are already quite a few good solutions, but I found they where slow, old and hard to read.
So I decided to add my solution which you can see below. While it looks simple, there are a few complexities that you may not catch at first glance.
const hierarchy = (
data = [],
{idKey='id',parentKey='parentId',childrenKey='children'} = {}
) => {
const tree = [];
const childrenOf = {};
data.forEach((item) => {
const { [idKey]: id, [parentKey]: parentId = 0 } = item;
childrenOf[id] = childrenOf[id] || [];
item[childrenKey] = childrenOf[id];
parentId
? (
childrenOf[parentId] = childrenOf[parentId] || []
).push(item)
: tree.push(item);
});
return tree;
}hierarchy(list, { idKey: 'Id', parentKey: 'Parent' });
Take a few minutes and try figure out what is going on in this function and how the tree is constructed; given that it’s only a single loop; where other answers had between 2 and 5 loops.
Let’s explain whats going on and how this works. But first I want to show that this solution is indeed the fastest from the other submitters
The differences are noticeable even on a set of 45 items, image this on 10,000 record set.
—
Let’s explain line by line whats is going on.
const hierarchy = (
data = [],
{idKey='id',parentKey='parentId',childrenKey='children'} = {}
) => {
....
}We are creating an arrow function called hierarchy and accepting two parameters:
First one is data (the list) and its default value is[] (empty array) in case nothing is provided, the code wont crash. You can specify default values in functions by using the = operator. Learn more about default parameter values.
The second parameter is a bit more complicated and looks like it has several parameters.
{idKey='id', parentKey='parentId', childrenKey='children'} = {}The second parameter doesn't have a name, I will call it options. While it appears complicated at first, it’s not. What is actually going on here is setting the default values for an object values, its funky to read at first.
Let’s create a more basic example to illustrate whats going on.
const person = ({ fname: 'bob', lname: 'neil'} = {}) => {
console.log(fname, lname);
}person(); // bob neil
person({ name: tom }}; // tom neil
person({ surname: 'owhn' }); // bob owhn
person({}); // bob neil
So as you can see it makes a bit more logical sense when broken down and its used for setting object default values in our example. Next:
const tree = [];
const childrenOf = {};Initialise tree and childrenOf to be used by loop to store pointers and the final object. And then we begin the loop:
data.forEach((item) => { const { [idKey]: id, [parentKey]: parentId = 0 } = item;
Again, we are using object destructuring and naming the values e.g by set [idKey]: id will translate to: const id = item['id'] , similar with the parentId except we are using the default value of 0 also.
childrenOf[id] = childrenOf[id] || [];This where the fun really begins, all we appear to be doing here is setting the value of itself or an empty[] and we are, but this will play a vital role later on.
item[childrenKey] = childrenOf[id];Remember item[childrenKey] is just the same as writing item['children'] but we want to allow the user to choose what childrenKey is.
We then assign the value of childrenOf[id] which we created above as a hash map. The important thing here is that childrenOf is an object of objects and when you point to its value, that creates a javascript pointer and not a copy, so for example on loop number X, we might only then be actually populating that value.
parentId
? (childrenOf[parentId] = childrenOf[parentId] || []).push(item)
: tree.push(item);We are using the shot-hand version of an if statement boolean ? true : false and when theres is a parentId present, meaning this item is child item, we need to add it to its parent.
So we look for childrenOf[parentId] if it exists we use that reference pointer and if not create an empty array, the only reason we do this is if the list comes back unorganised and a child item is before a parent item, we must initialize it.
Then once we determined if it exists or not, we push that item to it, as it’s a child item to that parent.
The second part is tree.push(item); remember, tree is the final object that returned and we only push root item to it (ones without a parent).
return tree;And we are done.
Now it might be still hard to imagine whats going on, so i’ve created a bit of console log output that can visualize how the items are added on each step of the loop. See the console output vs the code to understand better whats going on.
LOOP.0
item: {"Id":"1", "Name":"abc","Parent":""}
tree: [],
childrenOf: {},
LOOP.1:
item: {"Id":"2", "Name":"abc", "Parent":"1"}
tree: [{
"Id":"1",
"Name":"abc",
"Parent":"",
"children":[]
}],
childrenOf: {
"1":[]
},
LOOP.2:
item: {"Id":"3","Name":"abc","Parent":"2"}
tree: [{
"Id":"1",
"Name":"abc",
"Parent":"",
"children":[{
"Id":"2",
"Name":"abc",
"Parent":"1",
"children":[]
}]
}],
childrenOf: {
"1":[{
"Id":"2",
"Name":"abc",
"Parent":"1",
"children":[]
}],
"2":[]
},
LOOP.3:
item: {"Id":"4","Name":"abc","Parent":"2"}
tree: [{
"Id":"1",
"Name":"abc",
"Parent":"","
children":[{
"Id":"2",
"Name":"abc",
"Parent":"1",
"children":[{
"Id":"3",
"Name":"abc",
"Parent":"2",
"children":[]
}]
}]
}],
childrenOf: {
"1":[{
"Id":"2",
"Name":"abc",
"Parent":"1",
"children":[{
"Id":"3",
"Name":"abc",
"Parent":"2",
"children":[]
}]
}],
"2":[{
"Id":"3",
"Name":"abc",
"Parent":"2",
"children":[]
}],
"3":[]
}
FINAL RESULT:
tree: {
"Id": "1",
"Name": "abc",
"Parent": "",
"children": [
{
"Id": "2",
"Name": "abc",
"Parent": "1",
"children": [
{
"Id": "3",
"Name": "abc",
"Parent": "2",
"children": []
},
{
"Id": "4",
"Name": "abc",
"Parent": "2",
"children": []
}
]
}
]
}Happy hacking!
