A brief discussion on an efficient algorithm for constructing tree structures in JavaScript

introduction

We often encounter tree-like data structures, such as organizational hierarchies, provinces, cities, counties, or animal and plant classifications. The following is an example of a tree structure:

In practical applications, it is common to store this information as the following structure, especially when there is a one-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 do we convert this object array format into a hierarchical tree format? In fact, using the characteristics of JavaScript object references, it is very simple to implement. It can be done in O(n) time without recursion.

the term

For the sake of convenience, let us first define a few terms. We call each element in the array (that is, each circle in the tree diagram) a "node". A node can be the "parent node" of multiple nodes, or the "child node" of a certain node. In the above figure, node 86 is the “parent node” of node 80 and node 87, and node 86 is the child node of node 74. The topmost node of the tree is called the "root node".

Ideas

To construct the tree structure, we need:

• Traverse the data array
• Find the parent element of the current element
• Add a reference to the child element on the parent element object
• If an element has no parent, we consider it to be the root node of the tree.

We can see that references are stored in the object tree, which is why we can complete this task in O(n) time!

Establish ID-array index mapping relationship

Although it is not required, this mapping relationship can help us quickly find the location of the element and facilitate finding the reference to the parent element.

const idMapping = data.reduce((acc, el, i) => {
  acc[el.id] = i;
  return acc;
}, {});

The mapping results are as follows, and you will see how useful it is later:

{

56: 0,

62: 7,

63: 4,

74: 2,

76: 3,

80: 5,

81: 1,

86: 8,

87: 6,

};

Constructing a tree structure

Now we start constructing this tree structure. Iterate through the array of objects, find the parent object of each element, and then add a reference to the element. Now you should see how convenient this idMapping is for locating elements (constant time).

let root;
data.forEach(el => {
  // Determine the root node if (el.parentId === null) {
    root = el;
    return;
  }
  // Use the mapping table to find the parent element const parentEl = data[idMapping[el.parentId]];
  // Add the current element to the `children` array of the parent element parentEl.children = [...(parentEl.children || []), el];
});

Done! Use console.log to print root and see:

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 },

],

},

],

};

principle

Why is this possible? This is because each element in the data array is a reference to an object in memory, the el variable in the forEach loop actually points to an object in memory, and parentEl also references an object.

If an object in memory references a children array, these child elements can also reference their own child element arrays. These associations are all completed through references.

Summarize

Object reference is one of the most fundamental concepts in JavaScript and requires more learning and understanding. Once you truly understand this concept, you can avoid tricky bugs and come up with relatively simple solutions to seemingly complex problems.

The above is a brief discussion of the details of an efficient algorithm for constructing tree structures in JavaScript. For more information on JavaScript algorithms for constructing tree structures, please pay attention to other related articles on 123WORDPRESS.COM!