Introduction
Let’s say we have a tree data structure. This could be an organizational hierarchy, project breakdown, animal/plant taxonomy, etc. The following is an example of a tree structure:
In an application, it would be fairly common to store this information in the following format, especially if there is a 1-to-many parent/child node relationship:
const data = [
{ id: 56, parentId: 62 },
{ id: 81, parentId: 80 },
{ id: 74, parentId: null },
{ id: 76, parentId: 80 },
{ id: 63, parentId: 62 },
{ id: 80, parentId: 86 },
{ id: 87, parentId: 86 },
{ id: 62, parentId: 74 },
{ id: 86, parentId: 74 },
];
So how would we go from this array-of-objects format into a hierarchical tree format? This actually becomes a fairly easy task when you take advantage JavaScript object references. It can be done without recursion and in O(n) time.
Some Quick Terminology
To make sure we’re speaking the same language, let’s quickly go over some terminology I might use. Each element in our array (i.e., each circle on our tree) is a “node.” A node can be a “parent” of multiple nodes and a “child” of one node. In the picture above, node 86 is the “parent” of node 80 and node 87. node 86 is the “child” of node 74. The top node of our tree is the “root.”
The Overall Methodology
To build our tree, we’re going to want to:
- Iterate through the data array
- Find the parent element of the current element
- In the parent element’s object, add a reference to the child
- If there is no parent for an element, we know that will be our tree’s “root” element
We must realize that references will be maintained down the object tree, which is why we can accomplish this in O(n) time!
Making an ID-to-Array Position Map
While it’s not completely necessary, let’s start by creating a mapping of our element IDs to array index. This will help us add references to an element’s parent when the time comes.
const idMapping = data.reduce((acc, el, i) => {
acc[el.id] = i;
return acc;
}, {});
This mapping will come out as follows. You’ll soon see why this is helpful to have.
{
56: 0,
62: 7,
63: 4,
74: 2,
76: 3,
80: 5,
81: 1,
86: 8,
87: 6,
};
Creating the Tree
We’re ready to create our tree! Let’s iterate through the object and assign references to each item’s parent. Note where we use our idMapping to help us locate the parent.
let root;
data.forEach(el => {
// Handle the root element
if (el.parentId === null) {
root = el;
return;
}
// Use our mapping to locate the parent element in our data array
const parentEl = data[idMapping[el.parentId]];
// Add our current el to its parent's `children` array
parentEl.children = [...(parentEl.children || []), el];
});
And… that’s it! We can console.log our tree root to confirm:
console.log(root);
{
id: 74,
parentId: null,
children: [
{
id: 62,
parentId: 74,
children: [{ id: 56, parentId: 62 }, { id: 63, parentId: 62 }],
},
{
id: 86,
parentId: 74,
children: [
{
id: 80,
parentId: 86,
children: [{ id: 81, parentId: 80 }, { id: 76, parentId: 80 }],
},
{ id: 87, parentId: 86 },
],
},
],
};
Why this Works
The best way to understand why this works is to remember that each element of the data array is a reference to an object in memory, the el variable in our forEach loop is referencing an object in memory (the corresponding object in memory that the data array element is referencing), and parentEl is referencing an object in memory as well (again, one of the objects that’s being referenced in the data array).
If an object in memory has an array of children references, those children can have their own growing array of children references. Since this is all done by reference, you don’t need to tell parents anything when you’re modifying one of its children.
Conclusion
Object references is one of those foundational concepts in JavaScript that I believe can always use more study and understanding. Really getting this concept can both help avoid tricky bugs and provide for relative simply solutions to seemingly-complex problems.
Top comments (1)
Can we create tree if there are few nodes with same id? for example 50 is root node, has child 40,30 and 40 has child 20,10 likewise 30 has child 60,70.
now the 20 node has child of 30,50 and 10 has child of 40,20.
in a nut shell:
node name -- children
50 - 40,30
40 - 20,10
30 - 60,70
20 - 30,50
10 - 40,20