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!

Nina Scholz · Accepted Answer · 2022-03-03 08:31:20Z

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

CertainPerformance · Accepted Answer · 2022-03-02 21:34:50Z

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

Wow, this is great and the added tip of using constant time access from a predefined map is a great idea as well instead searching from an array. Thank you so much for your help, appreciate it

Scott Sauyet · Accepted Answer · 2022-03-02 23:14:09Z

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.

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related