JavaScript - build a tree data structure recursively

Question

I have a function called tree, which takes array of objects (as data fields from a database) and array of strings for keys. The function loops through rowsArray and recursively creates object with nested properties based on keyArray.

const tree = (rowsArray, keysArray) => {
  return rows.reduce((acc, row) => {
    const groupBy = (row, keys,) => {
      const [first, ...rest] = keys;

      if (!first) return [row];

      return {
        [row[first]]: groupBy(row, rest),
      }
    };
    acc = {...groupBy(row, keys), ...acc};
    return acc;
  }, {});
}

The data is following:

const data = [{
        ID: 1,
        Main: "Financial",
        Sub: "Forecasts",
        Detail: "General"
    }, {
        ID: 2,
        Main: "Financial",
        Sub: "HR",
        Detail: "Headcount"
}];

const result1 = tree(data, ["Main", "Sub", "Detail"]);
console.log(result1);

When I log the result, I get:

/*
// actual output
  { 
    Financial: { 
      Forecasts:  { 
        General: [Array] 
      } 
    } 
  }

Whereas, I would like to get following:

  // expected
  { 
    Financial: { 
      Forecasts:  { 
        General: [Array] 
      },
      HR:  { 
        Headcount: [Array] 
      }
    } 
  }
  */

The problem is, that acc variable in main function gets overridden and I get new object, instead of accumulative and I am not quite sure how to recursively build this object. I tried to pass instances of acc to groupBy function (to remember previous results), but no luck.

Do you have any idea how I could rewrite tree function or groupBy function to accomplish my goal? Thanks!

Would you be happy with a possible solution using a functional library? — customcommander, Nov 11 '18 at 13:42
What is supposed to be `[Array]`? (it is not valid JS format). Do those arrays contain anything? — trincot, Nov 11 '18 at 13:44
Hey, of course, functional libs are allowed :) [ Array ] is correct, yet shorthand output of the last array in the tree and it contains all the properties of original object from flat array. — Rafał Bagrowski, Nov 11 '18 at 14:09

score 2 · Answer 1 · answered Nov 11 '18 at 13:58

You could do it like this:

function tree(rows, keys) {
    return rows.reduce( (acc, row) => {
        keys.reduce( (parent, key, i) =>
            parent[row[key]] = parent[row[key]] || (i === keys.length - 1 ? [row] : {})
        , acc);
        return acc;
    }, {});
}

const data = [{ID: 1,Main: "Financial",Sub: "Forecasts",Detail: "General"}, {ID: 2,Main: "Financial",Sub: "HR", Detail: "Headcount" }];
const result1 = tree(data, ["Main", "Sub", "Detail"]);
console.log(result1);

Be aware that the spread syntax makes a shallow copy. Instead, in this solution, the accumulator is passed to the inner reduce. And so we actually merge the new row's hierarchical data into the accumulator on-the-spot.

score 1 · Accepted Answer · answered Nov 11 '18 at 13:57

The problem is your merge function is not deep. When you assign the values to the accumulator you overwrite existing properties - in this case Financial.

I included a deep merge function from here and now it works.

I also fixed some reference errors you had:

rows => rowsArray
keys = keysArray

// deep merge function
function merge(current, update) {
  Object.keys(update).forEach(function(key) {
    // if update[key] exist, and it's not a string or array,
    // we go in one level deeper
    if (current.hasOwnProperty(key) &&
      typeof current[key] === 'object' &&
      !(current[key] instanceof Array)) {
      merge(current[key], update[key]);

      // if update[key] doesn't exist in current, or it's a string
      // or array, then assign/overwrite current[key] to update[key]
    } else {
      current[key] = update[key];
    }
  });
  return current;
}

const tree = (rowsArray, keysArray) => {
  return rowsArray.reduce((acc, row) => {
    const groupBy = (row, keys, ) => {
      const [first, ...rest] = keys;

      if (!first) return [row];

      return {
        [row[first]]: groupBy(row, rest),
      }
    };
    acc = merge(groupBy(row, keysArray), acc);
    return acc;
  }, {});
}

const data = [{
  ID: 1,
  Main: "Financial",
  Sub: "Forecasts",
  Detail: "General"
}, {
  ID: 2,
  Main: "Financial",
  Sub: "HR",
  Detail: "Headcount"
}];

const result1 = tree(data, ["Main", "Sub", "Detail"]);
console.log(result1);

Hey, thank you. I am accepting this as solution. Merge deep is definitely great suggestion. Out of curiosity, do you think we could somehow adjust groupBy function to recursively merge deep this object on the fly? — Rafał Bagrowski, Nov 11 '18 at 15:28

Nina Scholz · Answer 3 · 2018-11-11T14:09:39.357

1

You could iterate the keys and take either an object for not the last key or an array for the last key and push then the data to the array.

const tree = (rowsArray, keysArray) => {
    return rowsArray.reduce((acc, row) => {
        keysArray
            .map(k => row[k])
            .reduce((o, k, i, { length }) => o[k] = o[k] || (i + 1 === length ? []: {}), acc)
            .push(row);
        return acc;
    }, {});
}

const data = [{ ID: 1, Main: "Financial", Sub: "Forecasts", Detail: "General" }, { ID: 2, Main: "Financial", Sub: "HR", Detail: "Headcount" }];

const result1 = tree(data, ["Main", "Sub", "Detail"]);
console.log(result1);

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

edited Nov 11 '18 at 14:09

answered Nov 11 '18 at 14:03

Nina Scholz

376,160
25
347
392

Thanks! Would you be able to explain how this fragment works? o[k] = o[k]? How does the function know how to create nested object? – Rafał Bagrowski Nov 11 '18 at 15:12
it takes an object as accumulator `o` and takes a default value if `o[k]` is falsy, then it assigns an array or object. this is returned as new accumulator. – Nina Scholz Nov 11 '18 at 15:15

score 1 · Answer 4 · answered Nov 11 '18 at 14:13

You can iterate over the data and created a unique key based on the keys provided and then recursively generate the output structure by deep cloning.

const data = [{
        ID: 1,
        Main: "Financial",
        Sub: "Forecasts",
        Detail: "General"
    }, {
        ID: 2,
        Main: "Financial",
        Sub: "HR",
        Detail: "Headcount"
}];

function generateKey(keys,json){
   return keys.reduce(function(o,i){
      o += json[i] + "_";
      return o;
   },'');
}

function merge(first,second){
 for(var i in second){
   if(!first.hasOwnProperty(i)){
      first[i] = second[i];
   }else{
      first[i] = merge(first[i],second[i]);
   }
 }
 return first;
}

function generateTree(input,keys){
  let values = input.reduce(function(o,i){
      var key = generateKey(keys,i);
      if(!o.hasOwnProperty(key)){
         o[key] = [];
      }
      o[key].push(i);
      return o;
  },{});

  return Object.keys(values).reduce(function(o,i){
     var valueKeys = i.split('_');
     var oo = {};
     for(var index = valueKeys.length -2; index >=0 ;index--){
        var out = {};
        if(index === valueKeys.length -2){
           out[valueKeys[index]] = values[i];
        }else{
           out[valueKeys[index]] = oo;
        }
        oo = out;
     }
     o = merge(o,oo);
     return o;
  },{});
}

console.log(generateTree(data,["Main", "Sub", "Detail"]));

jsFiddle Demo - https://jsfiddle.net/6jots8Lc/

JavaScript - build a tree data structure recursively

4 Answers4