Creating a hierarchical list structure from a one-dimensional list using parent and child relationships in JavaScript

Question

Creating a hierarchical list structure from a one-dimensional list using parent and child relationships in JavaScript

I am in the process of developing a web application that requires handling nested geographical data for display in a treeview and search functionality. The initial raw data structure resembles this:

id:1, name:UK
id:2: name: South-East, parentId: 1
id:3: name: South-West, parentId:1
id:4: name: Berkshire, parentId: 2
id:5: name: Reading, parentId: 4

The desired output format is as follows:

id:1: name UK, children[ 
 {id: 2, name: South-East, children:[
    {id:4: name: Berkshire, children: [
       {id:5: name: Reading}
     ]
  }, 
   {id:3: name: South-West}
]

In this structure, each geographical location includes a "children" array property containing sub-areas with their own "children" array property. It might be beneficial to include a "parent" property for easy navigation from child items to their parent.

Additionally, I require search functionality for the list. Given that searching through the entire treeview could be time-consuming, maintaining a flat list format alongside the nested structure could be helpful.

While I have an idea of how to implement this using JavaScript (potentially utilizing jLinq for filtering, grouping, and sorting), I am uncertain about its efficiency. Are there any existing implementations in JavaScript or known algorithms/patterns that address this issue?

javascript algorithm

Answer 1

Answer №1

Converting a flat array into a tree structure can be done efficiently with a few simple steps. The key is to optimize the data structure definition to make the process faster. Lazy loading can also play a role in speeding up the operation.

This JavaScript code snippet demonstrates how to achieve this:

    //Optimize the data structure definition for efficiency..
    //Each entry consists of [name, parent_position_in_array]..
    //Ensure parent nodes are defined before child nodes..
    var data = [
        ["Root", -1], //top level node..
        ["Branch A", 0],
        ["Branch B", 0],
        ["Node X", 1],
        ["Leaf Y", 3]
        //Add more entries as needed...
    ];

    //Converts a flat array into a tree and returns the root node..
    //(Assumes child nodes follow their respective parent nodes)
    function createTree(array){
        var treeArray = new Array(array.length);

        for(var index = 0; index < array.length; index++){
            var currentItem = array[index];
            var newNode = treeArray[index] = {
                name: currentItem[0],
                children: []
            };
            var parentIndex = currentItem[1];
            
            if(parentIndex > -1){ 
                treeArray[parentIndex].children.push(newNode);
            }
        }

        return treeArray[0]; //return the root node..
    }

    var rootNode = createTree(data);

To evaluate the performance on a larger dataset, you can use the following test:

    var testData = [['root', -1]];
    
    for(var i = 1; i < 100000; i++){
        var randomParentIndex = Math.floor(Math.random() * (i-1));
        testData.push(['child_node', randomParentIndex]);   
    }

    var startTime = new Date().getTime();
    var resultingTree = createTree(testData);
    var endTime = new Date().getTime();

    console.log('Execution time: ' + (endTime - startTime) + 'ms.');

On a typical desktop machine, processing 100000 elements takes less than 200ms. It's important to consider what level of performance is satisfactory for your specific application needs!

Answer 2

Converting a flat array into a tree structure can be done efficiently with a few simple steps. The key is to optimize the data structure definition to make the process faster. Lazy loading can also play a role in speeding up the operation.

This JavaScript code snippet demonstrates how to achieve this:

    //Optimize the data structure definition for efficiency..
    //Each entry consists of [name, parent_position_in_array]..
    //Ensure parent nodes are defined before child nodes..
    var data = [
        ["Root", -1], //top level node..
        ["Branch A", 0],
        ["Branch B", 0],
        ["Node X", 1],
        ["Leaf Y", 3]
        //Add more entries as needed...
    ];

    //Converts a flat array into a tree and returns the root node..
    //(Assumes child nodes follow their respective parent nodes)
    function createTree(array){
        var treeArray = new Array(array.length);

        for(var index = 0; index < array.length; index++){
            var currentItem = array[index];
            var newNode = treeArray[index] = {
                name: currentItem[0],
                children: []
            };
            var parentIndex = currentItem[1];
            
            if(parentIndex > -1){ 
                treeArray[parentIndex].children.push(newNode);
            }
        }

        return treeArray[0]; //return the root node..
    }

    var rootNode = createTree(data);

To evaluate the performance on a larger dataset, you can use the following test:

    var testData = [['root', -1]];
    
    for(var i = 1; i < 100000; i++){
        var randomParentIndex = Math.floor(Math.random() * (i-1));
        testData.push(['child_node', randomParentIndex]);   
    }

    var startTime = new Date().getTime();
    var resultingTree = createTree(testData);
    var endTime = new Date().getTime();

    console.log('Execution time: ' + (endTime - startTime) + 'ms.');

On a typical desktop machine, processing 100000 elements takes less than 200ms. It's important to consider what level of performance is satisfactory for your specific application needs!

Answer 3

Answer №2

When dealing with a simple id and parent-id objects array without any additional information about the hierarchy level, it can be challenging to create a nested structure. Traditional recursive methods may not be efficient for long lists. One effective approach I have discovered involves sorting the array in a specific order where children follow their parents. Even though parents, children, and root objects may be mixed, ensuring that each child follows its parent is crucial. Assuming the object structure resembles something like this:

var data = [{id: KL442, pid: HN296}, {id: ST113, pid: HN296}, {id: HN296, pid: "root"},...]

. Sorting is just the initial step of the process. During the sorting process, creating a Look Up Table (LUT) comes in handy for easy access to parents. With a single instruction at the end of the outer loop lut[a[i].id]=i;, accessing parents becomes incredibly fast during the nesting phase. This marks the completion of the sorting and LUT preparation phase.

function sort(a){
  var len = a.length,
      fix = -1;
  for (var i = 0; i < len; i++ ){
      while(!!~(fix = a.findIndex(e => a[i].pid == e.id)) && fix > i) [a[i],a[fix]] = [a[fix],a[i]];
      lut[a[i].id]=i;
  }
  return a;
}

Once the array is sorted, performing a reverse iteration is all that's required to achieve the nested structure. With the data array sorted and LUT prepared, the following code handles the nesting:

for (var i = sorted.length-1; i>=0; i--)
    sorted[i].pid != "root" && (!! sorted[lut[sorted[i].pid]].children
                                && sorted[lut[sorted[i].pid]].children.push(sorted.splice(i,1)[0])
                                || (sorted[lut[sorted[i].pid]].children = [sorted.splice(i,1)[0]]));

For a practical demonstration, you can refer to an earlier response of mine on Stack Overflow.

Answer 4

When dealing with a simple id and parent-id objects array without any additional information about the hierarchy level, it can be challenging to create a nested structure. Traditional recursive methods may not be efficient for long lists. One effective approach I have discovered involves sorting the array in a specific order where children follow their parents. Even though parents, children, and root objects may be mixed, ensuring that each child follows its parent is crucial. Assuming the object structure resembles something like this:

var data = [{id: KL442, pid: HN296}, {id: ST113, pid: HN296}, {id: HN296, pid: "root"},...]

. Sorting is just the initial step of the process. During the sorting process, creating a Look Up Table (LUT) comes in handy for easy access to parents. With a single instruction at the end of the outer loop lut[a[i].id]=i;, accessing parents becomes incredibly fast during the nesting phase. This marks the completion of the sorting and LUT preparation phase.

function sort(a){
  var len = a.length,
      fix = -1;
  for (var i = 0; i < len; i++ ){
      while(!!~(fix = a.findIndex(e => a[i].pid == e.id)) && fix > i) [a[i],a[fix]] = [a[fix],a[i]];
      lut[a[i].id]=i;
  }
  return a;
}

Once the array is sorted, performing a reverse iteration is all that's required to achieve the nested structure. With the data array sorted and LUT prepared, the following code handles the nesting:

for (var i = sorted.length-1; i>=0; i--)
    sorted[i].pid != "root" && (!! sorted[lut[sorted[i].pid]].children
                                && sorted[lut[sorted[i].pid]].children.push(sorted.splice(i,1)[0])
                                || (sorted[lut[sorted[i].pid]].children = [sorted.splice(i,1)[0]]));

For a practical demonstration, you can refer to an earlier response of mine on Stack Overflow.

Answer 5

Answer №3

Using Lodash Library:

var keyMap = _.mapKeys(data,'key');
var result = {};
_.each(keyMap, function(value){
  if(!value.parentKey){
    result[value.key] = value;
  }else{
    if(!keyMap[value.parentKey].children){
      keyMap[value.parentKey].children=[];
    }
    keyMap[value.parentKey].children.push(value);
  }
});

Check out the live demo here

Answer 6

Using Lodash Library:

var keyMap = _.mapKeys(data,'key');
var result = {};
_.each(keyMap, function(value){
  if(!value.parentKey){
    result[value.key] = value;
  }else{
    if(!keyMap[value.parentKey].children){
      keyMap[value.parentKey].children=[];
    }
    keyMap[value.parentKey].children.push(value);
  }
});

Check out the live demo here

Creating a hierarchical list structure from a one-dimensional list using parent and child relationships in JavaScript

Answer №1

Answer №2

Answer №3

Similar questions

The time zones between Node 8 and Node 11 are not the same

Extracting props data from a component in React.js - a step-by-step guide

The Mongoose connection pool has been shut down

Retrieve the AJAX response, concatenate the data, and construct a dynamic table

Exploring methods for monitoring page transitions in Next.js

Looking for assistance in implementing specific styling techniques with React

How to use multiple template urls in Angular 6

Can you guide me on implementing an onclick event using HTML, CSS, and JavaScript?

Using vue.js to make an HTTP GET request to a web API URL and display

FilterService of PrimeNg

Difficulty with Pomodoro clock's canvas ring function not working as expected

Steps for mocking an async action creator in Redux using Jest

retrieving the value of an object key based on changing information

Tips on choosing and showcasing information from jQuery date and time picker

Is it possible to alter the state of one page by clicking a link on another page?

Tips for managing a PHP post request without full knowledge of the variables to retrieve

Unable to properly execute Fetch Delete Request

When working with THREE.js in Electron, web development tools seem to vanish into thin air

Issue with Axios code execution following `.then` statement

What is the best way to utilize the "useRouter" function to extract parameters from the URL within the getServerSideProps() method in Next.js?