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!

Answer 1

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/

Answer 2

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

Answer 3

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.

Answer 4

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