How to Efficiently Convert a Flat Array of JSON Objects into a Hierarchical Tree Structure in JavaScript?

Converting a Flat Array to a Hierarchical Tree Structure in JavaScript

In JavaScript, we often encounter situations where we need to organize data hierarchically. One common representation is a tree structure, where nodes are interconnected with parent-child relationships. This article explores an efficient technique for converting a flat array of JSON objects into such a hierarchical tree structure.

Problem Description

Given an array of JSON objects, each representing a node in the tree, with properties like "id," "parentId," "level," and "text," we aim to convert this flat array into a nested JSON object where each node contains an array of its children.

Solution

One effective approach involves utilizing a map-lookup algorithm. By creating a map that associates each node's "id" with its corresponding index in the array, we can efficiently traverse the array and build the hierarchical structure.

Firstly, we initialize the map and ensure that each node has an empty "children" array to store its descendants. Then, we iterate over the array and for each node, we check its "parentId." If it's not "0," we locate the parent node using its "id" from the map and append the current node as a child. Nodes with "parentId" as "0" represent the roots of the tree.

This solution's key advantages are its efficiency and its ability to handle multiple roots. It doesn't rely on external libraries and can handle dangling branches (child nodes without a parent).

Here's a JavaScript code snippet implementing this solution:

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

Using the provided sample input, the function will generate the expected hierarchical output, as demonstrated in the example below:

var entries = [{
        "id": "12",
        "parentId": "0",
        "text": "Man",
        "level": "1",
        "children": null
      },
      {
        "id": "6",
        "parentId": "12",
        "text": "Boy",
        "level": "2",
        "children": null
      },
      {
        "id": "7",
        "parentId": "12",
        "text": "Other",
        "level": "2",
        "children": null
      },
      {
        "id": "9",
        "parentId": "0",
        "text": "Woman",
        "level": "1",
        "children": null
      },
      {
        "id": "11",
        "parentId": "9",
        "text": "Girl",
        "level": "2",
        "children": null
      }
    ];

console.log(list_to_tree(entries));

This approach provides a straightforward and efficient solution to build hierarchical tree structures from flat arrays, meeting the requirements of your data management and visualization needs.

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