Building Deep Trees in JavaScript Using Object References
Tags: javascript, webdev, programming, tutorials
Published: 2020-05-07 12:12:23

---
title: Building Deep Trees in JavaScript Using Object References 
published: true
description: Building a tree structure in JavaScript can be easy if you think in terms of references.
tags: javascript, webdev, programming, tutorials
cover_image: https://i.imgur.com/kpShASg.png
canonical_url: https://typeofnan.dev/an-easy-way-to-build-a-tree-with-object-references/
---

#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:

![tree](https://i.imgur.com/kpShASg.png)

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:

```javascript
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.

```javascript
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.

```javascript
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:

```javascript
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.