How to Efficiently Build a Hierarchical Tree from a Flat Array in JavaScript?

Building a Hierarchical Tree from a Flat Array in JavaScript

In JavaScript, there are situations where you may need to transform a flat array of objects representing a hierarchical structure into a nested tree structure. This can arise when working with complex JSON data, as in the provided example.

To build a tree structure, we utilize a map-based approach. This method is efficient and supports multiple root nodes. It requires that the parent nodes precede their children in the flat array.

Here's how we implement this in JavaScript:

function list_to_tree(list) {
  var map = {}, node, roots = [], i;

  for (i = 0; i < list.length; i += 1) {
    map[list[i].id] = i; // initialize the map
    list[i].children = []; // initialize the children
  }

  for (i = 0; i < list.length; i += 1) {
    node = list[i];
    if (node.parentId !== "0") {
      // if you have dangling branches check that map[node.parentId] exists
      list[map[node.parentId]].children.push(node);
    } else {
      roots.push(node);
    }
  }
  return roots;
}

var entries = //Your flat array of entries

console.log(list_to_tree(entries));

This solution initializes a map map that stores the indices of each node's ID, ensuring quick lookup. It then iterates through the list twice. In the first pass, it initializes each node's children property to an empty array. In the second pass, it builds the tree structure by attaching nodes to their respective parent nodes using the data from the map. If a node has a parentId of "0," it is considered a root node and is added to an array of roots. Finally, the list_to_tree function returns an array of root nodes.

The above is the detailed content of How to Efficiently Build a Hierarchical Tree from a Flat Array in JavaScript?. For more information, please follow other related articles on the PHP Chinese website!