Order list of object based on parent child association in JS

Question

I am trying to create a loop that will go though an array of objects and order them in a way where if the object is a child of a parent then it is placed into a children array and then the original object is removed from the list. I have it kind of working but it fails for children of children and so on. It will fail if it's parent is already a child of another object. How can I modify this to accomplish the above?

Here is what I have:

for (const obj of objects) {
  const children = objects.filter(d => d.parentId === obj.id);
  obj.children = children;

  for (const child of children) {
    const objIndex = objects.findIndex(d => d.id === child.id);
    if (objIndex > -1) objects.splice(objIndex, 1);
  }
}

So if the input is:

const objects = [
  { id: 85, parentId: null },
  { id: 86, parentId: 85 },
  { id: 87, parentId: 86 },
  { id: 88, parentId: 86 }
];

The result should be:

[
  {
    id: 85, children: [
      {
        id: 86, children: [
          { id: 87 },
          { id: 88 }
        ]
      }
    ]
  }
];

But it's not what I get is:

[
  { id: 85, children: [{ id: 86 }]},
  { id: 87 },
  { id: 88 },
]

I see why this is happening I am just not sure of how to fix it since technically you can nest infinitely. Any thoughts here?

Answer 1

I'd go trough each node, find the parent and add itself to the parent's children.

Then filter out the non-root nodes (the ones with a parentId).

const objects = [
  { id: 85, parentId: null },
  { id: 86, parentId: 85 },
  { id: 87, parentId: 86 },
  { id: 88, parentId: 86 }
];

let hierarchy = objects.map(obj=>({...obj}));

for(let i=0;i<hierarchy.length;i++){
  const cur=hierarchy[i];
  if(cur.parentId){
    const parent = hierarchy.find(({id})=>id===cur.parentId);
    parent.children = [...(parent.children || []), cur];
  }
}

hierarchy=hierarchy.filter(({parentId})=>!parentId);


console.log(hierarchy);