How to construct a tree of objects from an array of objects (unflatten an array)

Question

I currently have a flat array of objects which I am trying to convert to a nested array of objects. I would like to reuse this function throughout my application - whatever the final depth of the array - so I believe a recursive function would be more appropriate.

My attemps so far I have been a combination of sort + reduce with no success.

It would be much appreciated if you could help me write a clean function for my app !

Initial Array - Flat list of objects

const data = [
  { index: 0, parentKey: '-LLnMWy69vACjys0QIGH', type: 'options', name: 'OPTION_1', key: '-LLnOxg5hsDYR-PcfjBT' },
  { index: 1, parentKey: '-LLnMWy69vACjys0QIGH', type: 'options', name: 'OPTION_2', key: '-LLnP-O6TyHxIpPk9bCU' },
  { index: 0, parentKey: '-LLnLuLt6cn-vBpMWv-u', type: 'collections', name: 'COLLECTION_1', key: '-LLnMWy69vACjys0QIGH' },
  { index: 1, parentKey: '-LLnLuLt6cn-vBpMWv-u', type: 'collections', name: 'COLLECTION_2', key: '-LLnMYNyJmhSCPB-8lL1' },
  { index: 0, name: 'CONFIGURATOR_1', key: '-LLnLuLt6cn-vBpMWv-u' },
  { index: 1, name: 'CONFIGURATOR_2', key: '-LLnLtLs7PjXSAW0PWCQ' },
];

Desired outcome - Nested arrays of objects

const data = [
  {
    key: '-LLnLuLt6cn-vBpMWv-u',
    name: 'CONFIGURATOR_1',
    collections: [
      {
        key: '-LLnMWy69vACjys0QIGH',
        name: 'COLLECTION_1',
        options: [
          {
            key: '-LLnOxg5hsDYR-PcfjBT',
            name: 'OPTION_1',
          },
          {
            key: '-LLnP-O6TyHxIpPk9bCU',
            name: 'OPTION_2',
          },
        ],
      },
      {
        key: '-LLnMYNyJmhSCPB-8lL1',
        name: 'COLLECTION_2',
      },
    ],
  },
  { key: '-LLnLtLs7PjXSAW0PWCQ',
    name: 'CONFIGURATOR_2',
}]

score 0 · Answer 1 · answered Sep 09 '18 at 02:00

As usual for this problem, one of the simplest method is to index all object by key with a map M.

then, go through the map M, if the current keyed element has a parent, then add it to the keyed parent in the Map M then map all these elements to an array A. Since all objects in javascript are references, the tree structure would be reconstructed automatically.

The last step would be to filter out all elements in A that have a parent.

const data = [
    { index: 0, parentKey: '-LLnMWy69vACjys0QIGH', type: 'options', name: 'OPTION_1', key: '-LLnOxg5hsDYR-PcfjBT' },
    { index: 1, parentKey: '-LLnMWy69vACjys0QIGH', type: 'options', name: 'OPTION_2', key: '-LLnP-O6TyHxIpPk9bCU' },
    { index: 0, parentKey: '-LLnLuLt6cn-vBpMWv-u', type: 'collections', name: 'COLLECTION_1', key: '-LLnMWy69vACjys0QIGH' },
    { index: 1, parentKey: '-LLnLuLt6cn-vBpMWv-u', type: 'collections', name: 'COLLECTION_2', key: '-LLnMYNyJmhSCPB-8lL1' },
    { index: 0, name: 'CONFIGURATOR_1', key: '-LLnLuLt6cn-vBpMWv-u' },
    { index: 1, name: 'CONFIGURATOR_2', key: '-LLnLtLs7PjXSAW0PWCQ' },
];

const M = data.reduce(function (result, el) {
    result[el.key] = el
    return result;
}, {});
const A = Object.keys(M).map(key => {
    const el = M[key]
    if (M[el.parentKey]) {
        if (!M[el.parentKey].collections) {
            M[el.parentKey].collections = []
        }
        M[el.parentKey].collections.push(el)
    }
    return el
}).filter(el => {
    return !el.parentKey
})

console.log(JSON.stringify(A, null, '\t'))

Thanks for your help mpm. Much appreciated! Your earlier comments helped me to solve my issue! They seem to have disappeared! For anyone that faces a similar issue, the solution that helped me was : https://stackoverflow.com/questions/18017869/build-tree-array-from-flat-array-in-javascript — Julien, Sep 09 '18 at 08:24

score 0 · Answer 2 · answered Sep 09 '18 at 08:21

I have found my issue using the following function. I am sure there is other ways more efficient ways to do it but it is the cleanest option i have found!

const objectNest = (array, parentKey) => {
  const output = [];
  array.forEach((object) => {
    if (object.parentKey === parentKey) {
      const children = objectNest(array, object.key);
      if (children.length) { object[children[0].type] = children; }
      const { index, parentKey, ...content } = object;
      output.push(content);
    }
  });
  return output;
};

How to construct a tree of objects from an array of objects (unflatten an array)

2 Answers2