What's the most efficient method to recursively nest an array of objects into a tree structure with the id serving as a reference point?

Question

What's the most efficient method to recursively nest an array of objects into a tree structure with the id serving as a reference point?

My goal is to organize the pages in my database in a hierarchical "tree" view. Each page has a unique ID and a parent property that indicates which page it is a child of.

I am looking for an efficient way to recursively nest these objects so that each child page is nested within its appropriate parent page based on the parent ID reference. Here is the initial array:

[ 
    { 
        _id: 1,
        title: 'Page A-1',
        parent: null 
    },
    { 
        _id: 2,
        title: 'Page A-2',
        parent: 1 
    },
    { 
        _id: 3,
        title: 'Page A-3',
        parent: 2 
    },
    { 
        _id: 4,
        title: 'Page A-4',
        parent: 3 
    },
    { 
        _id: 5,
        title: 'Page A-5',
        parent: 4 
    },
    { 
        _id: 6,
        title: 'Page B-1',
        parent: null 
    },
    { 
        _id: 7,
        title: 'Page B-2',
        parent: 6 
    },
    { 
        _id: 8,
        title: 'Page B-3',
        parent: 7 
    },
    { 
        _id: 9,
        title: 'Page B-4',
        parent: 8 
    },
    { 
        _id: 10,
        title: 'Page B-5',
        parent: 8 
    },
    { 
        _id: 11,
        title: 'Page C-1',
        parent: null
    }
]

The desired transformed array would look like this:

[ 
    { 
        _id: 1,
        title: 'Page A-1',
        children: [
            { 
                _id: 2,
                title: 'Page A-2',
                children: [
                    { 
                        _id: 3,
                        title: 'Page A-3',
                        children: [
                            { 
                                _id: 4,
                                title: 'Page A-4',
                                children: [
                                    { 
                                        _id: 5,
                                        title: 'Page A-5',
                                        children: [

                                        ]
                                    }       
                                ]
                            }       
                        ]
                    }
                ]
            }       
        ]
    },
    { 
        _id: 6,
        title: 'Page B-1',
        children: [
            { 
                _id: 7,
                title: 'Page B-2',
                children: [
                    { 
                        _id: 8,
                        title: 'Page B-3',
                        children: [
                            { 
                                _id: 9,
                                title: 'Page B-4',
                                children: []
                            },
                            { 
                                _id: 10,
                                title: 'Page B-5',
                                children: []
                            }
                        ]
                    }       
                ]
            }
        ]
    },
    { 
        _id: 11,
        title: 'Page C-1',
        children: []
    }
]

javascript json recursion

Answer 1

Answer №1

Instead of focusing on the necessity for this task, I will share with you a highly efficient approach in terms of big-O complexity.

This algorithm consists of three steps with linear complexity O(items.length), making the entire process linear as well.

It's worth noting that in this tradeoff, I prioritize time complexity over space efficiency.

Step 1:

Start by iterating through your items and creating a Map<id, object>:

// You could also utilize a POJO here
// For demonstration purposes, I'm using a map as the data structure 
const map = items.reduce((map, item) => {
  map.set(item._id, item);
  // To avoid potential issues, consider not using original objects when building the tree
  // Instead, create new objects as shown in step 2 below
  /*
    map.set(item._id, {
      ...item,
      children: []
    })
  */
  return map;
}, new Map())

Step 2:

Proceed to iterate through the items and organize them under their respective parent:

items.forEach(item => {
  if (item.parent) {
    const parent = map.get(item.parent);
    // Modifying original objects can lead to bugs, so consider creating new objects in step 1
    if (!parent.children) {
      parent.children = [];
    }
    parent.children.push(item);
  }
})

Step 3:

Lastly, iterate through the items in the map and retrieve the top-level parents:

const result = [];
for (const item of map.values()) {
  if (!item.parent) {
    result.push(item);
  }
}

For your reference, here's a complete example:

const items=[{_id:1,title:"Page A-1",parent:null},{_id:2,title:"Page A-2",parent:1},{_id:3,title:"Page A-3",parent:2},{_id:4,title:"Page A-4",parent:3},{_id:5,title:"Page A-5",parent:4},{_id:6,title:"Page B-1",parent:null},{_id:7,title:"Page B-2",parent:6},{_id:8,title:"Page B-3",parent:7},{_id:9,title:"Page B-4",parent:8},{_id:10,title:"Page B-5",parent:8},{_id:11,title:"Page C-1",parent:null}];

// Step 1
const map = items.reduce((map, item) => {
  map.set(item._id, item);
  return map;
}, new Map())

// Step 2
items.forEach(item => {
  if (item.parent) {
    const parent = map.get(item.parent);
    if (!parent.children) {
      parent.children = [];
    }
    parent.children.push(item);
  }
})

// Step 3
const result = [];
for (const item of map.values()) {
  if (!item.parent) {
    result.push(item);
  }
}

console.log(result);

Keep in mind that while algorithmic complexity is crucial, actual implementation details and the efficiency of operations and data structures used also impact performance. For optimal results, benchmark testing may be necessary to fine-tune the algorithm.

Answer 2

Instead of focusing on the necessity for this task, I will share with you a highly efficient approach in terms of big-O complexity.

This algorithm consists of three steps with linear complexity O(items.length), making the entire process linear as well.

It's worth noting that in this tradeoff, I prioritize time complexity over space efficiency.

Step 1:

Start by iterating through your items and creating a Map<id, object>:

// You could also utilize a POJO here
// For demonstration purposes, I'm using a map as the data structure 
const map = items.reduce((map, item) => {
  map.set(item._id, item);
  // To avoid potential issues, consider not using original objects when building the tree
  // Instead, create new objects as shown in step 2 below
  /*
    map.set(item._id, {
      ...item,
      children: []
    })
  */
  return map;
}, new Map())

Step 2:

Proceed to iterate through the items and organize them under their respective parent:

items.forEach(item => {
  if (item.parent) {
    const parent = map.get(item.parent);
    // Modifying original objects can lead to bugs, so consider creating new objects in step 1
    if (!parent.children) {
      parent.children = [];
    }
    parent.children.push(item);
  }
})

Step 3:

Lastly, iterate through the items in the map and retrieve the top-level parents:

const result = [];
for (const item of map.values()) {
  if (!item.parent) {
    result.push(item);
  }
}

For your reference, here's a complete example:

const items=[{_id:1,title:"Page A-1",parent:null},{_id:2,title:"Page A-2",parent:1},{_id:3,title:"Page A-3",parent:2},{_id:4,title:"Page A-4",parent:3},{_id:5,title:"Page A-5",parent:4},{_id:6,title:"Page B-1",parent:null},{_id:7,title:"Page B-2",parent:6},{_id:8,title:"Page B-3",parent:7},{_id:9,title:"Page B-4",parent:8},{_id:10,title:"Page B-5",parent:8},{_id:11,title:"Page C-1",parent:null}];

// Step 1
const map = items.reduce((map, item) => {
  map.set(item._id, item);
  return map;
}, new Map())

// Step 2
items.forEach(item => {
  if (item.parent) {
    const parent = map.get(item.parent);
    if (!parent.children) {
      parent.children = [];
    }
    parent.children.push(item);
  }
})

// Step 3
const result = [];
for (const item of map.values()) {
  if (!item.parent) {
    result.push(item);
  }
}

console.log(result);

Keep in mind that while algorithmic complexity is crucial, actual implementation details and the efficiency of operations and data structures used also impact performance. For optimal results, benchmark testing may be necessary to fine-tune the algorithm.

Answer 3

Answer №2

While looping through the array, I recommend creating a lookup of all objects and assigning children to parents within the same loop. This method eliminates the need to search for parents in the tree, assuming the data size is manageable enough to avoid memory issues.

[Please note: The assumption here is that parents are defined before children in the array. If not, some additional work will be necessary within the loop.]

let info = [
    {
        id: 1,
        name: 'Item A-1',
        parent: null
    },
    {
        id: 2,
        name: 'Item A-2',
        parent: 1
    },
    {
        id: 3,
        name: 'Item A-3',
        parent: 2
    },

    {
        id: 4,
        name: 'Item A-4',
        parent: 3
    },
    {
        id: 5,
        name: 'Item A-5',
        parent: 4
    },
    {
        id: 6,
        name: 'Item B-1',
        parent: null
    },
    {
        id: 7,
        name: 'Item B-2',
        parent: 6
    },
    {
        id: 8,
        name: 'Item B-3',
        parent: 7
    },
    {
        id: 9,
        name: 'Item B-4',
        parent: 8
    },
    {
        id: 10,
        name: 'Item B-5',
        parent: 8
    },
    {
        id: 11,
        name: 'Item C-1',
        parent: null
    }
]

let index = {}
let structure = {}

info.forEach(element => {
    let itemObject = {id: element.id, name: element.name, children: []}

    if (!index[element.id]) index[element.id] = itemObject

    if (!element.parent) {
        structure[element.id] = itemObject
    } else {
        index[element.parent].children.push(itemObject)
    }
})
console.log(structure)

Answer 4

While looping through the array, I recommend creating a lookup of all objects and assigning children to parents within the same loop. This method eliminates the need to search for parents in the tree, assuming the data size is manageable enough to avoid memory issues.

[Please note: The assumption here is that parents are defined before children in the array. If not, some additional work will be necessary within the loop.]

let info = [
    {
        id: 1,
        name: 'Item A-1',
        parent: null
    },
    {
        id: 2,
        name: 'Item A-2',
        parent: 1
    },
    {
        id: 3,
        name: 'Item A-3',
        parent: 2
    },

    {
        id: 4,
        name: 'Item A-4',
        parent: 3
    },
    {
        id: 5,
        name: 'Item A-5',
        parent: 4
    },
    {
        id: 6,
        name: 'Item B-1',
        parent: null
    },
    {
        id: 7,
        name: 'Item B-2',
        parent: 6
    },
    {
        id: 8,
        name: 'Item B-3',
        parent: 7
    },
    {
        id: 9,
        name: 'Item B-4',
        parent: 8
    },
    {
        id: 10,
        name: 'Item B-5',
        parent: 8
    },
    {
        id: 11,
        name: 'Item C-1',
        parent: null
    }
]

let index = {}
let structure = {}

info.forEach(element => {
    let itemObject = {id: element.id, name: element.name, children: []}

    if (!index[element.id]) index[element.id] = itemObject

    if (!element.parent) {
        structure[element.id] = itemObject
    } else {
        index[element.parent].children.push(itemObject)
    }
})
console.log(structure)

What's the most efficient method to recursively nest an array of objects into a tree structure with the id serving as a reference point?

Answer №1

Answer №2

Similar questions

RegEx unable to extract a number ranging from 0 to 23

Updating the database with values dynamically using ajax without the need to refresh or change the current page

"Limitation observed - function operates only on first attempt

Tips for testing a mapbox popup using jasmine testing?

When I request the value of a JavaScript object, I am met with 'undefined'

How to export multiple dictionaries into a single CSV file with a shared header using Python

"Trouble arose when I tried to incorporate additional functions into my JavaScript code; my prompt feature is not

Troubleshooting issue with changing class based on input values

I need assistance from someone knowledgeable in HTML and CSS. I am trying to create a div that dynamically increases its width until it reaches a specific

What steps can be taken to repair the script?

Overlapping agendas within Microsoft Planner

Converting the given data into an object in JavaScript: a step-by-step guide

The ng-disabled directive in AngularJS fails to disable the button as expected

Unable to install vue-property-decorator

Display the name of the file on the screen

PHP REST API to handle requests and generate corresponding responses

Creating dynamic qtip2 tooltips is an effective way to enhance user interaction on

Unraveling Vue Async Components - Harnessing the power of emitted events to resolve

What is the most effective way to transfer an array from one PHP file to a different JavaScript file?

Vue JS: dynamic reactive structure