Create a hierarchy of arrays from a flat array

Question

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?

Are you trying to avoid a solution to go through array and then create the object in a for loop? — Shameel Uddin, May 18 '22 at 14:54
"The `id` is actually not a number in my actual app. It's a random string BTW." Please update your question to replace number id with strings to avoid confusion for people who don't read that line — Samathingamajig, May 18 '22 at 14:54
Is it always guaranteed that there will be ***exactly one*** element with no parent? — Samathingamajig, May 18 '22 at 14:55
@Samathingamajig there could be an object with a parent but the parent isn't in the array. In that case, it's the root object — Arno, May 18 '22 at 14:59
@Arno So the conditions for root are: 1) No `parent` value, OR 2) `parent` value not in the elements? And there can never be a case where there are multiple that meet this condition? — Samathingamajig, May 18 '22 at 15:03
@Samathingamajig no, it is the root object. The one with a parent id that isn't in the array is the root object — Arno, May 18 '22 at 15:04
Does this answer your question? [Build tree array from flat array in javascript](https://stackoverflow.com/questions/18017869/build-tree-array-from-flat-array-in-javascript) — Tomty, May 18 '22 at 15:10

Samathingamajig · Accepted Answer · 2022-05-18T15:06:13.187

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));

RenaudC5 · Answer 2 · 2022-05-18T15:35:46.837

0

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

edited May 18 '22 at 15:35

answered May 18 '22 at 14:59

RenaudC5

3,553
1
11
29

Crashes when there is "an object with a parent but the parent isn't in the array" – Samathingamajig May 18 '22 at 15:07
Might be better now – RenaudC5 May 18 '22 at 15:35

score 0 · Answer 3 · answered May 18 '22 at 15:16

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)

Create a hierarchy of arrays from a flat array

3 Answers3