What is the best way to recursively nest an Array of Objects into a tree using the id as a reference?

Question

I'm trying to create a "tree" view of all the pages in my database. To do this I've given each page a "parent" property along with a unique id of the page it is a child of.

Now I'd like to recursively nest this Array of Objects inside of itself so that all the child pages are nested inside their appropriate parent pages. Using the parent id as a reference, what is the most efficient way to transform the following Array from this:

[ 
    { 
        _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
    }
]

into 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: []
    }
]

Answer 1

My answer will disregard the necessity for doing this and give you the most time-efficient approach in terms of big-O complexity.

The algorithms contains three steps of linear complexity O(items.length), which makes the entire algorithm linear as well.

Note: As is the common tradeoff, I'm sacrificing space to achieve optimal time complexity.

Step 1):

Iterate through your items and build a Map<id, object>:

// you can also use a POJO here
// i'm using a map to demonstrate the appropriate data structure
const map = items.reduce((map, item) => {
  map.set(item._id, item);
  // Note: it might be safer to not use original objects when building the tree
  // and create new objects instead. See the comment in step 2 as well.
  /*
    map.set(item._id, {
      ...item,
      children: []
    })
  */
  return map;
}, new Map())

Step 2)

Iterate through your items and nest each under its parent.

items.forEach(item => {
  if (item.parent) {
    const parent = map.get(item.parent);
    // Note: this will actually edit your original objects
    // Since mutability is the cause of many bugs, if you can afford it
    // I'd create new objects with the children property in step 1
    // when inserting items into the map which would make this if
    // statement redundant
    if (!parent.children) {
      parent.children = [];
    }
    parent.children.push(item);
  }
})

Step 3)

Iterate through the items in the map and take the top-level parents:

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

Here's a full 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);

In the real world, performance depends not only on the algorithmic complexity, but on the actual implementation details for all operations and data-structures used. If such critical performance matters to you, building an optimal algorithm would require actual benchmark testing.

Answer 2

I would make a lookup of all objects as you loop through the array and add children to parents in the same loop. Assuming your data isn't so large that have memory issues, you can do it in one loop through the array without having to search the tree for parents.

[note: this assumes parents are defined before children in the array. if not you'll have to do a little more work in the loop (but not much)]

let data = [
    {
        _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
    }
]

let lookup = {}
let tree = {}

data.forEach(item => {
    let obj = {_id: item._id, title: item.title, children: [] }
    // add to lookup
    if(!lookup[item._id]) lookup[item._id] =  obj

    if(!item.parent) {
        // a root node. Add directly to tree
        tree[item._id] = obj
    } else{
        //  a child node. Add to parent's children array
        lookup[item.parent].children.push(obj)
    }
})
console.log(tree)