Turning flat array of objects into nested tree (location data)

Hi so I want to transform a given flat array of objects (loc. dataset) into a tree-like structure with repeating keys.

NOTE: my actual input data is about 140K elements of objects with exactly same 4 keys as listed below.

Input sample:

[
   {
      "continent_name":"Asia",
      "country_name":"Iran",
      "subdivision_1_name":"Chaharmahal and Bakhtiari Province",
      "city_name":"Lir Abi"
   },
   {
      "continent_name":"Europe",
      "country_name":"Cyprus",
      "subdivision_1_name":"Ammochostos",
      "city_name":"Protaras"
   },
   {
      "continent_name":"Asia",
      "country_name":"Iran",
      "subdivision_1_name":"West
Azerbaijan Province",
      "city_name":"Post"
   },
   {
      "continent_name":"Africa",
      "country_name":"Somalia",
      "subdivision_1_name":"Bakool",
      "city_name":"Oddur"
   }
]

Output sample:

[
        {
           label: "Asia",
           children: [
               {
                   label: 'Iran',
                   children: [
                       {
                           label: 'Chaharmahal and Bakhtiari Province',
                           children: [
                               {
                                  label: 'Lir Abi',
                                  children: []
                               }
                           ]
                       },
                       {
                          label: 'West Azerbaijan Province',
                          children: [
                              {
                                 label: 'Post',
                                 children: []
                              }
                          ]
                       }
                   ]
               }
           ]
        },
        {
          label: "Africa",
          children: [
              {
                  label: 'Somalia',
                  children: [
                      {
                          label: 'Bakool',
                          children: [
                              {
                                  label: 'Oddur',
                                  children: []
                              }
                          ]
                      }
                  ]
              }
          ]
        },
        {
          label: "Europe",
          children: [
              {
                  label: 'Cyprus',
                  children: [
                      {
                          label: 'Ammochostos',
                          children: [
                              {
                                  label: 'Protaras',
                                  children: []
                              }
                          ]
                      }
                  ]
              }
          ]
        }
    ]

And this is the code I was trying to use:

    const returnTree = []
    function unflatten(data, property, returnArr) {
        for (let i = 0; i < data.length; i++) {
            const currObj = data[i];
            const currContinent = data[i][property]
            let continentIdx = returnArr.findIndex(obj => obj.label === currContinent)
            if (continentIdx === -1) {
                continentIdx = returnArr.length
                returnArr.push({
                    'label': currContinent,
                    'children': [currObj]
                })
            } else {
                returnArr[continentIdx].children.push(currObj)
            }
            // exceeed max call stack if I continue even one more level in
            unflatten(returnArr[continentIdx].children, 'country_name', returnTree)
        }
        console.log(returnArr)
        return returnArr
    }
    unflatten(inputData, 'continent_name', returnTree)

The problem I have is I exceed max call stack using this recursive method and I am wondering if there is a better way to handle this, perhaps iteratively?

Any help would be appreciated! Thank you!

>Solution :

I don’t think recursion is the way to go here, because for each property value (to make an object out of), there’s exactly one place in the generated structure that it could be. While iterating over properties, keep the last outer array in an outer variable, and you can .find to see if a matching object has already been inserted – if it hasn’t, then create one.

const input=[{continent_name:"Asia",country_name:"Iran",subdivision_1_name:"Chaharmahal and Bakhtiari Province",city_name:"Lir Abi"},{continent_name:"Europe",country_name:"Cyprus",subdivision_1_name:"Ammochostos",city_name:"Protaras"},{continent_name:"Asia",country_name:"Iran",subdivision_1_name:"West Azerbaijan Province",city_name:"Post"},{continent_name:"Africa",country_name:"Somalia",subdivision_1_name:"Bakool",city_name:"Oddur"}];

const output = [];
for (const obj of input) {
  let nestedArr = output;
  for (const [key, value] of Object.entries(obj)) {
    const existingInnerObj = nestedArr.find(({ label }) => label === value);
    if (existingInnerObj) {
      nestedArr = existingInnerObj.children;
    } else {
      const newObj = { label: value, children: [] };
      nestedArr.push(newObj);
      nestedArr = newObj.children;
    }
  }
}
console.log(output);

You could decrease the complexity by either saving the created objects in a map or object indexed by label, or by creating them in objects to begin with, then transforming them into an array later (this will turn the O(n) operation of .find into O(1) of property lookup).