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

Question

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!

Answer 1

Another approach with an object as hash table and result sets for each children array.

const
    data = [{ 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" }],
    keys = ["continent_name", "country_name", "subdivision_1_name", "city_name"],
    result = data
        .reduce((r, o) => {
            keys.reduce(function (q, k) {
                const label = o[k];
                if (!q[label]) q._.push({ label, children: (q[label] = { _: [] })._ });
                return q[label];
            }, r);
            return r;
        }, { _: [] })
        ._;

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

This version is configured with the list of keys you want to nest on, and it recurs with each key. It's recursion is only on the levels of the resulting tree. If that has recursion depth problems, then there are many more important problems to deal with. ?

const omitting = (prop) => ({[prop]: p, ...rest}) => rest

const group = (fn) => (xs) => Object .values (xs .reduce 
  ((a, x, _, __, k = fn (x)) => ((a [k] = a [k] || []), (a [k] .push (x)), a), 
  {}
))

const labelGroup = ([label, ...labels]) => (xs) => 
  label == undefined
    ? xs
    : group (x => x [label]) (xs) .map (ys => ({
        label: ys [0] [label], 
        children: labelGroup (labels) (
          ys .map (omitting (label)) .filter (x => Object .keys (x) .length)
        )
      }))

const divisions = [{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 labels = ['continent_name', 'country_name', 'city_name', 'subdivision_1_name']

console .log (
  labelGroup (labels) (divisions)
)

.as-console-wrapper {max-height: 100% !important; top: 0}

We start with two helper functions:

• omitting returns a copy of an object with the specified key omitted.

• group accepts a key-generation function, and returns a function that takes an array of values and groups them into subarrays each of which map to a single key.

The main function labelGroup takes a list of labels to group upon and returns a function which takes an array of values, and recursively groups these into groups that share a label, mapping the results by extracting the common label, omitting the current key from each, and returning the recursive result of applying labelGroup to them with the remaining keys. The recursion bottoms out when there are no labels left to extract.

The only tricky bit of this, is the filter call before the recursive application. We use it to remove entirely empty objects. This gives you the results you want when you group on every single label in the objects, as done here, but also allows you to group on a smaller list of labels. So if you passed just 'continent_name' and 'countryName', you would get something like this:

    {
        "label": "Asia",
        "children": [
            {
                "label": "Iran",
                "children": [
                    {
                        "subdivision_1_name": "Chaharmahal and Bakhtiari Province",
                        "city_name": "Lir Abi"
                    },
                    {
                        "subdivision_1_name": "West Azerbaijan Province",
                        "city_name": "Post"
                    }
                ]
            }
        ]
    },
    /* ... */
}

I think this is a fairly flexible technique. We might make it still more flexible by allowing us to group on composite keys or select multiple fields that show up at each level, and we might make the fields label and children configurable. But that's for another day.