Create a hierarchy of arrays from a flat array-CodePudding

Consider I have an array like this

const ar = [
  {id: 1, name: "A", parent: null},
  {id: 2, name: "B", parent: 1},
  {id: 11, name: "AA", parent: 1},
  {id: 12, name: "AB", parent: 1},
  {id: 111, name: "AAA", parent: 11},
  {id: 41, name: "CC", parent: 4},
  {id: 4, name: "C", parent: 1},
];

How do I create a hierarchy of just one object like this

{
    id: 1,
    name: "A",
    parent: null,
    children: [
      {
        id: 11,
        name: "AA",
        parent: 1,
        children: [
          {id: 111, name: "AAA", parent: 11}],
      },
      {id: 2, name: "B", parent: 1, children: []},
      {
        id: 4,
        name: "C",
        parent: 1,
        children: [{id: 41, name: "CC", parent: 4, children: []}],
      },
    ],
  }

The id is actually not a number in my actual app. It's a random string BTW.

I could do it recursively by drilling through the children array but it is not the most effective way. Can somebody help please?

CodePudding user response：

const ar = [
  {id: 1, name: "A", parent: null},
  {id: 2, name: "B", parent: 1},
  {id: 11, name: "AA", parent: 1},
  {id: 12, name: "AB", parent: 1},
  {id: 111, name: "AAA", parent: 11},
  {id: 41, name: "CC", parent: 4},
  {id: 4, name: "C", parent: 1},
];

const hierarchy = (arr) => {
  const map = {};
  let root;
  for (const ele of arr) {
    map[ele.id] = ele;
    ele.children = [];
  }
  for (const ele of arr) {
    if (map[ele.parent] != undefined)
      map[ele.parent].children.push(ele);
    else
      root = ele;
  }
  return root;
}

console.log(hierarchy(ar));

CodePudding user response：

First step is to map the items by the id so you have an easy look up so you are not looping over the array multiple times. After that you just need to loop over and add a children array to the parent and add the reference.

const ar = [
  {id: 1, name: "A", parent: null},
  {id: 2, name: "B", parent: 1},
  {id: 11, name: "AA", parent: 1},
  {id: 12, name: "AB", parent: 1},
  {id: 111, name: "AAA", parent: 11},
  {id: 41, name: "CC", parent: 4},
  {id: 4, name: "C", parent: 1},
];

// make a look up by the id
const mapped = ar.reduce((acc, item) => {
  acc[item.id] = item;
  return acc;
}, {});

// loop over
const result = ar.reduce((acc, item) => {
  // if there there is no parent, we know it is the first so return it
  const parentId = item.parent;
  if (!parentId) return item;
  
  // if we have a parent, see if we found this yet, if not add the array
  mapped[parentId].children = mapped[parentId].children || []; 
  // set the item as a child
  mapped[parentId].children.push(item);
  
  return acc;
}, null);

console.log(result)

CodePudding user response：

You can iterate through the array and push the elem to the right place each time.

To get the root, you can then retrieve the element without parent.

const arr = [{id: 1, name: "A", parent: null},
  {id: 2, name: "B", parent: 1},
  {id: 11, name: "AA", parent: 1},
  {id: 12, name: "AB", parent: 1},
  {id: 111, name: "AAA", parent: 11},
  {id: 41, name: "CC", parent: 4},
  {id: 4, name: "C", parent: 1}]
  
arr.forEach(elem => elem.children = [])
  
  arr.forEach(elem => {
    if(elem.parent){
      const parent = arr.find(x => x.id === elem.parent)
      if(parent)parent.children.push(elem)
    }
  })
  
  console.log(arr.find(x => !x.parent))

Note : If you want to optimize a little more, you can add the children array in the second forEach