Convert array of flat objects to nested objects

I have the following array (that’s actually coming from a backend service):

const flat: Item[] = [
    { id: 'a', name: 'Root 1', parentId: null },
    { id: 'b', name: 'Root 2', parentId: null },
    { id: 'c', name: 'Root 3', parentId: null },

    { id: 'a1', name: 'Item 1', parentId: 'a' },
    { id: 'a2', name: 'Item 1', parentId: 'a' },

    { id: 'b1', name: 'Item 1', parentId: 'b' },
    { id: 'b2', name: 'Item 2', parentId: 'b' },
    { id: 'b2-1', name: 'Item 2-1', parentId: 'b2' },
    { id: 'b2-2', name: 'Item 2-2', parentId: 'b2' },
    { id: 'b3', name: 'Item 3', parentId: 'b' },

    { id: 'c1', name: 'Item 1', parentId: 'c' },
    { id: 'c2', name: 'Item 2', parentId: 'c' }
];

where Item is:

interface Item {
    id: string;
    name: string;
    parentId: string;
};

In order to be compatible with a component that displays a tree (folder like) view, it needs to be transformed into:

const treeData: NestedItem[] = [
    {
        id: 'a',
        name: 'Root 1',
        root: true,
        count: 2,
        children: [
          {
            id: 'a1',
            name: 'Item 1'
          },
          {
            id: 'a2',
            name: 'Item 2'
          }
        ]
    },
    {
        id: 'b',
        name: 'Root 2',
        root: true,
        count: 5, // number of all children (direct + children of children)
        children: [
          {
            id: 'b1',
            name: 'Item 1'
          },
          {
            id: 'b2',
            name: 'Item 2',
            count: 2,
            children: [
                { id: 'b2-1', name: 'Item 2-1' },
                { id: 'b2-2', name: 'Item 2-2' },
            ]
          },
          {
            id: 'b3',
            name: 'Item 3'
          },
        ]
    },
    {
        id: 'c',
        name: 'Root 3',
        root: true,
        count: 2,
        children: [
          {
            id: 'c1',
            name: 'Item 1'
          },
          {
            id: 'c2',
            name: 'Item 2'
          }
        ]
    }
];

where NestedItem is:

interface NestedItem {
    id: string;
    name: string;
    root?: boolean;
    count?: number;
    children?: NestedItem[];
}

All I’ve tried so far is something like:

// Get roots first
const roots: NestedItem[] = flat
    .filter(item => !item.parentId)
    .map((item): NestedItem => {
        return { id: item.id, name: item.name, root: true }
    });

// Add "children" to those roots
const treeData = roots.map(node => {
    const children = flat
        .filter(item => item.parentId === node.id)
        .map(item => {
            return { id: item.id, name: item.name }
        });
    return {
        ...node,
        children,
        count: node.count ? node.count + children.length : children.length
    }
});

But this only gets the first level of children, of course (direct children of root nodes). It somehow needs to be recursive, but I have no idea how to accomplish that.

Answer

Making no assumptions about the order of the flattened array or how deep a nested object can go:

Array.prototype.reduce is flexible enough to get this done. If you are not familiar with Array.prototype.reduce I recommend reading this. You could accomplish this by doing the following.

I have two functions that rely on recursion here: findParent and checkLeftOvers. findParent attempts to find the objects parent and returns true or false based on whether it finds it. In my reducer I add the current value to the array of left overs if findParent returns false. If findParent returns true I call checkLeftOvers to see if any object in my array of left overs is the child of the object findParent just added.

Note: I added { id: 'b2-2-1', name: 'Item 2-2-1', parentId: 'b2-2'} to the flat array to demonstrate that this will go as deep as you’d like. I also reordered flat to demonstrate that this will work in that case as well. Hope this helps.

const flat = [
    { id: 'a2', name: 'Item 1', parentId: 'a' },
    { id: 'b2-2-1', name: 'Item 2-2-1', parentId: 'b2-2'},
    { id: 'a1', name: 'Item 1', parentId: 'a' },
    { id: 'a', name: 'Root 1', parentId: null },
    { id: 'b', name: 'Root 2', parentId: null },
    { id: 'c', name: 'Root 3', parentId: null },
    { id: 'b1', name: 'Item 1', parentId: 'b' },
    { id: 'b2', name: 'Item 2', parentId: 'b' },
    { id: 'b2-1', name: 'Item 2-1', parentId: 'b2' },
    { id: 'b2-2', name: 'Item 2-2', parentId: 'b2' },
    { id: 'b3', name: 'Item 3', parentId: 'b' },
    { id: 'c1', name: 'Item 1', parentId: 'c' },
    { id: 'c2', name: 'Item 2', parentId: 'c' }
];

function checkLeftOvers(leftOvers, possibleParent){
  for (let i = 0; i < leftOvers.length; i++) {
    if(leftOvers[i].parentId === possibleParent.id) {
      delete leftOvers[i].parentId
      possibleParent.children ? possibleParent.children.push(leftOvers[i]) : possibleParent.children = [leftOvers[i]]
      possibleParent.count = possibleParent.children.length
      const addedObj = leftOvers.splice(i, 1)
      checkLeftOvers(leftOvers, addedObj[0])
    }
  }
}

function findParent(possibleParents, possibleChild) {
  let found = false
  for (let i = 0; i < possibleParents.length; i++) {
    if(possibleParents[i].id === possibleChild.parentId) {
      found = true
      delete possibleChild.parentId
      if(possibleParents[i].children) possibleParents[i].children.push(possibleChild)
      else possibleParents[i].children = [possibleChild]
      possibleParents[i].count = possibleParents[i].children.length
      return true
    } else if (possibleParents[i].children) found = findParent(possibleParents[i].children, possibleChild)
  } 
  return found;
}
 
 const nested = flat.reduce((initial, value, index, original) => {
   if (value.parentId === null) {
     if (initial.left.length) checkLeftOvers(initial.left, value)
     delete value.parentId
     value.root = true;
     initial.nested.push(value)
   }
   else {
      let parentFound = findParent(initial.nested, value)
      if (parentFound) checkLeftOvers(initial.left, value)
      else initial.left.push(value)
   }
   return index < original.length - 1 ? initial : initial.nested
 }, {nested: [], left: []})
 
console.log(nested)