Flat JSON to hierarchy/tree without ID

Question

Helloo, I'm trying to convert a flat JSON to a tree structure and I'm curious if this is possible or not. Any help completing my problem would be greatly appreciated.

Below is what I have currently tried and am working on. This only successfully get the first set of children and they're children. I haven't been able to make it passed this point. I fear this may not be possible.

I know the root before I started so I think it should be possible. For this case the root is "Provide Automated Military Health Systems Functions".

The tree JSON would end up looking like:

{ "name": "Provide Automated Military Health Systems Functions", "children": [ { "name": "Provide Infrastructure Support Functions", "children": [ "name": "Provide Data Management Functions" "children": [etc, etc] ] }, { "name": "Provide Clinical Support Functions", "children": [etc etc] }, { "name": "Provide Non-Clinical Support Functions", "children": [etc etc] } ] }

Here is the fiddle I've been working off of also: http://jsfiddle.net/ydgbkv39/

The fiddle does a console print of the first 2 levels but I can't seem to make it past that point.

Hopefully, someone can help me out!

var data = [
  {
    "Upstream": "Provide Automated Military Health Systems Functions",
    "Downstream": "Provide Infrastructure Support Functions"
  },
  {
    "Upstream": "Provide Automated Military Health Systems Functions",
    "Downstream": "Provide Clinical Support Functions"
  },
  {
    "Upstream": "Provide Automated Military Health Systems Functions",
    "Downstream": "Provide Non-Clinical Support Functions"
  },
  {
    "Upstream": "Provide Infrastructure Support Functions",
    "Downstream": "Provide Data Management Functions"
  },
  {
    "Upstream": "Provide Infrastructure Support Functions",
    "Downstream": "Provide Maintenance Utilities Functions"
  },
  {
    "Upstream": "Provide Infrastructure Support Functions",
    "Downstream": "Provide Business Rules Execution Functions"
  },
  {
    "Upstream": "Provide Infrastructure Support Functions",
    "Downstream": "Provide MHS Health Portal Functions"
  },
  {
    "Upstream": "Provide Infrastructure Support Functions",
    "Downstream": "Provide Security Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Care Management Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Nutrition Information Management Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Healthcare Specialty Services Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Lab Support Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Pharmacy Support Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Blood Management Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Medical Imagery Support Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Operations Support Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Order Results Care Management Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Medical Orders Maintenance Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Episodes of Care Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Executive Decision Support Management Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Manage Family Support Process Workflow (BEA)"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Health Records Support Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Resource Management Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Medical Readiness Management Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Population Health Management Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Medical Logistics Management Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Patient Directory Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Provider Information Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Patient Administration Functions"
  }
];

Array.prototype.diff = function(a) {
    return this.filter(function(i) {return a.indexOf(i) < 0;});
};

var upstreamArr = [];
var downstreamArr = [];
data.forEach(function (a) {
 upstreamArr.push(a.Upstream);
  downstreamArr.push(a.Downstream);
}, {});

var root = upstreamArr.diff(downstreamArr);
root = root[0];

var tree = {};
tree.name = root;
tree.children = [];

data.forEach(function (a) {
 if(a.Upstream === root) {
   if(tree.children.indexOf(a.Downstream) === -1) {
     tree.children.push(a.Downstream);
    }
  }
}, {});

function buildTree(d) {
 if(d.children.length > 0) {
   for(var i = 0; i < d.children.length; i++) {
     findKids(d, d.children[i]);
    }
  }
  return d;
}

function findKids(d, child) {
  let obj = {};
  obj.children = [];
 data.forEach(function (a) {
      if(a.Upstream === child) {
       obj.name = child;
        if(obj.children.indexOf(a.Downstream) === -1) {
          obj.children.push(a.Downstream);
        }
      }
    }, {});

 var ind = d.children.indexOf(child);
 return d.children[ind] = obj;
    
}


/*function eachRecursive(obj) {
    for (var k in obj) {
        if (typeof obj[k] == "object" && obj[k] !== null) {
         eachRecursive(obj[k]);
        } else {
        
        }
    }
}*/

console.log(buildTree(tree));

Just as a critic of the code, you should avoid modifying `Array.prototype.diff` because is a built-in type. [See this answer](https://stackoverflow.com/a/948379/266535) for more info. — styfle, Nov 01 '17 at 15:49

score 2 · Answer 1 · answered Nov 01 '17 at 17:01

You will need to use an object to map the key (in this case the 'name') to the value (in this case the tree node).

I named my functions so you can see how it works below:

var data = [
  {
    "Upstream": "Provide Automated Military Health Systems Functions",
    "Downstream": "Provide Infrastructure Support Functions"
  },
  {
    "Upstream": "Provide Automated Military Health Systems Functions",
    "Downstream": "Provide Clinical Support Functions"
  },
  {
    "Upstream": "Provide Automated Military Health Systems Functions",
    "Downstream": "Provide Non-Clinical Support Functions"
  },
  {
    "Upstream": "Provide Infrastructure Support Functions",
    "Downstream": "Provide Data Management Functions"
  },
  {
    "Upstream": "Provide Infrastructure Support Functions",
    "Downstream": "Provide Maintenance Utilities Functions"
  },
  {
    "Upstream": "Provide Infrastructure Support Functions",
    "Downstream": "Provide Business Rules Execution Functions"
  },
  {
    "Upstream": "Provide Infrastructure Support Functions",
    "Downstream": "Provide MHS Health Portal Functions"
  },
  {
    "Upstream": "Provide Infrastructure Support Functions",
    "Downstream": "Provide Security Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Care Management Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Nutrition Information Management Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Healthcare Specialty Services Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Lab Support Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Pharmacy Support Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Blood Management Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Medical Imagery Support Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Operations Support Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Order Results Care Management Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Medical Orders Maintenance Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Episodes of Care Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Executive Decision Support Management Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Manage Family Support Process Workflow (BEA)"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Health Records Support Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Resource Management Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Medical Readiness Management Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Population Health Management Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Medical Logistics Management Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Patient Directory Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Provider Information Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Patient Administration Functions"
  }
];


var nameToNode = {};

function getNodeByName(name) {
  if (!nameToNode[name]) {
    nameToNode[name] = { name: name, children: [] };
  }
  return nameToNode[name];
}

function getRootNode() {
  for (var name in nameToNode) {
    if (nameToNode[name].children.length > 0) {
      return nameToNode[name];
    }
  }
}

function buildTree() {
  data.forEach(o => {
    var up = getNodeByName(o.Upstream);
    var down = getNodeByName(o.Downstream);
    up.children.push(down);
  });
}

buildTree();
var root = getRootNode();
console.log(root);

The getRootNode function assumes all of the original records will form a single Tree. If you are expecting a forest with multiple root nodes, then you will need to change the logic a bit.

This works perfectly as long as the root node is the first element in the array just liek the other one. I chose the other answer instead because it didn't build empty arrays for the children property. But this answer worked great also. — CStreet, Nov 01 '17 at 18:57

JstnPwll · Accepted Answer · 2017-11-01T20:24:20.943

You can keep track of all the nodes by storing them in a "flat" object (where each items's name is its key in the flat object). If the name doesn't exist in the flat object yet, you create it; otherwise, you use its reference to add children.

var data = [
  {
    "Upstream": "Provide Infrastructure Support Functions",
    "Downstream": "Provide Data Management Functions"
  },
  {
    "Upstream": "Provide Infrastructure Support Functions",
    "Downstream": "Provide Maintenance Utilities Functions"
  },
  {
    "Upstream": "Provide Infrastructure Support Functions",
    "Downstream": "Provide Business Rules Execution Functions"
  },
  {
    "Upstream": "Provide Infrastructure Support Functions",
    "Downstream": "Provide MHS Health Portal Functions"
  },
  {
    "Upstream": "Provide Infrastructure Support Functions",
    "Downstream": "Provide Security Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Care Management Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Nutrition Information Management Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Healthcare Specialty Services Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Lab Support Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Pharmacy Support Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Blood Management Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Medical Imagery Support Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Operations Support Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Order Results Care Management Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Medical Orders Maintenance Functions"
  },
  {
    "Upstream": "Provide Clinical Support Functions",
    "Downstream": "Provide Episodes of Care Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Executive Decision Support Management Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Manage Family Support Process Workflow (BEA)"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Health Records Support Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Resource Management Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Medical Readiness Management Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Population Health Management Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Medical Logistics Management Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Patient Directory Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Provider Information Functions"
  },
  {
    "Upstream": "Provide Non-Clinical Support Functions",
    "Downstream": "Provide Patient Administration Functions"
  },
  {
    "Upstream": "Provide Automated Military Health Systems Functions",
    "Downstream": "Provide Infrastructure Support Functions"
  },
  {
    "Upstream": "Provide Automated Military Health Systems Functions",
    "Downstream": "Provide Clinical Support Functions"
  },
  {
    "Upstream": "Provide Automated Military Health Systems Functions",
    "Downstream": "Provide Non-Clinical Support Functions"
  }
];

var tree = {}, flat = {};

var setRoots = function(data){
  var unique = {};
  data.forEach(function(item){
    unique[item.Upstream] = true;
  });
  data.forEach(function(item){
    if(unique[item.Downstream]){
      delete unique[item.Downstream];
    }
  });
  var keys = Object.keys(unique), rootName = data[0].Upstream;
  if(keys.length == 1){
    rootName = keys[0];
  }
  tree = {name: rootName};
  flat[rootName] = tree;
}
var addItemToTree = function(item){
  var parent = flat[item.Upstream], child = flat[item.Downstream];
  if(!parent){
    parent = flat[item.Upstream] = { name: item.Upstream }
  }
  if(!child){
    child = flat[item.Downstream] = { name: item.Downstream };
  }
  if(!parent.children){
    parent.children = [];
  }
  parent.children.push(child);
}
setRoots(data);
data.forEach(addItemToTree);
console.log(tree);

This works perfectly as long as the root node is the first element in the array. I chose this answer instead of the other because this doesn't build empty arrays for the children property. — CStreet, Nov 01 '17 at 18:56
I've updated my answer to figure out the root based on the data rather than the order. — JstnPwll, Nov 01 '17 at 19:08
The use of `indexOf` inside a `forEach` makes this algorithm O(n^2). For large datasets, this answer could be significantly slower than my O(n) answer. — styfle, Nov 01 '17 at 19:48

Flat JSON to hierarchy/tree without ID

2 Answers2