Frank Myat Thu Frank Myat Thu - 6 months ago 19
Javascript Question

create dynamic nested json objects using recursive

I have following JSON.

[{
"ID": "Root_1",
"Name": "Root_1",
"ParentID": "",
"Sequent": 1
},
{
"ID": "Root_2",
"Name": "Root_2",
"ParentID": "",
"Sequent": 2
},
{
"ID": "Root_1_Sub_1_Child_1",
"Name": "Root_1_Sub_1_Child_1",
"ParentID": "Root_1_Sub_1",
"Sequent": 1
},
{
"ID": "Root_1_Sub_1_Child_2",
"Name": "Root_1_Sub_1_Child_2",
"ParentID": "Root_1_Sub_1",
"Sequent": 2
},
{
"ID": "Root_1_Sub_1",
"Name": "Root_1_Sub_1",
"ParentID": "Root_1",
"Sequent": 1
}]


I want to change my JSON to as following.

[{
"ID": "Root_1",
"Name": "Root_1",
"ParentID": "",
"Sequent": 1,
"Sub": [{
"ID": "Root_1_Sub_1",
"Name": "Root_1_Sub_1",
"ParentID": "Root_1",
"Sequent": 1,
"Sub": [{
"ID": "Root_1_Sub_1_Child_1",
"Name": "Root_1_Sub_1_Child_1",
"ParentID": "Root_1_Sub_1",
"Sequent": 1
},
{
"ID": "Root_1_Sub_1_Child_2",
"Name": "Root_1_Sub_1_Child_2",
"ParentID": "Root_1_Sub_1",
"Sequent": 2
}]
}]
},
{
"ID": "Root_2",
"Name": "Root_2",
"ParentID": "",
"Sequent": 2
}]


After I trying following way, the result is not what I want.

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<script src="./bower_components/angular/angular.min.js"></script>
<script>
angular.module('myApp', [])
.controller('MyCtrl', function($scope, $http) {

$scope.ProjectCategoryList_FlatStyle = [{
"ID": "Root_1",
"Name": "Root_1",
"ParentID": "",
"Sequent": 1
},
{
"ID": "Root_2",
"Name": "Root_2",
"ParentID": "",
"Sequent": 2
},
{
"ID": "Root_1_Sub_1_Child_1",
"Name": "Root_1_Sub_1_Child_1",
"ParentID": "Root_1_Sub_1",
"Sequent": 1
},
{
"ID": "Root_1_Sub_1_Child_2",
"Name": "Root_1_Sub_1_Child_2",
"ParentID": "Root_1_Sub_1",
"Sequent": 2
},
{
"ID": "Root_1_Sub_1",
"Name": "Root_1_Sub_1",
"ParentID": "Root_1",
"Sequent": 1
}];


$scope.ProjectCategoryList_TreeStyle = [];
$scope.ParentArray = [];
$scope.ConvertFlatToTree = function(Value){
angular.forEach(Value, function(item){

// Create row.
var _Object = new Object();
_Object.ID = item.ID;
_Object.Name = item.Name;
_Object.ParentID = item.ParentID;
_Object.Sequent = item.Sequent;
_Object.Sub = [];

// Checking if it is root element.
if(item.ParentID){
// It is for child node.
// Get Parent Element.
var ParentElement = $scope.ParentArray.filter(function (x) { return x.ID === item.ParentID; });
ParentElement[0].Sub.push(_Object);
$scope.ParentArray.push(_Object);
}else{
// It is for parent node.
// Get child elements.
var ChildElementArray = $scope.ProjectCategoryList_FlatStyle.filter(function (x) { return x.ParentID === item.ID; });
if(ChildElementArray.length != 0){
$scope.ParentArray.push(_Object);
$scope.ProjectCategoryList_TreeStyle.push(_Object);
$scope.ConvertFlatToTree(ChildElementArray);
}
}
})
console.log("ProjectCategoryList_TreeStyle = ", JSON.stringify($scope.ProjectCategoryList_TreeStyle));
}
$scope.ConvertFlatToTree($scope.ProjectCategoryList_FlatStyle);
});
</script>
</head>
<body ng-app="myApp" ng-controller="MyCtrl">
</body>
</html>


Below is my final result.

[{
"ID": "Root_1",
"Name": "Root_1",
"ParentID": "",
"Sequent": 1,
"Sub": [{
"ID": "Root_1_Sub_1",
"Name": "Root_1_Sub_1",
"ParentID": "Root_1",
"Sequent": 1,
"Sub": [{
"ID": "Root_1_Sub_1_Child_1",
"Name": "Root_1_Sub_1_Child_1",
"ParentID": "Root_1_Sub_1",
"Sequent": 1,
"Sub": []
},
{
"ID": "Root_1_Sub_1_Child_2",
"Name": "Root_1_Sub_1_Child_2",
"ParentID": "Root_1_Sub_1",
"Sequent": 2,
"Sub": []
}]
},
{
"ID": "Root_1_Sub_1",
"Name": "Root_1_Sub_1",
"ParentID": "Root_1",
"Sequent": 1,
"Sub": []
}]
}]


Plunker

Answer

Here is your solution. However it could have been much better if you had your ID and parentID naming conventions better. Instead of doing tons of recursive runs i just sorted the input data first then did the job sequentially.

var flat = [{
    "ID": "Root_1",
    "Name": "Root_1",                   
    "ParentID": "",
    "Sequent": 1
},
{
    "ID": "Root_2",
    "Name": "Root_2",                   
    "ParentID": "",
    "Sequent": 2
},              
{
    "ID": "Root_1_Sub_1_Child_1",
    "Name": "Root_1_Sub_1_Child_1",                 
    "ParentID": "Root_1_Sub_1",
    "Sequent": 1
},
{
    "ID": "Root_1_Sub_1_Child_2",
    "Name": "Root_1_Sub_1_Child_2",                 
    "ParentID": "Root_1_Sub_1",
    "Sequent": 2
},
{
    "ID": "Root_1_Sub_1",
    "Name": "Root_1_Sub_1",                 
    "ParentID": "Root_1",
    "Sequent": 1
}];
function nested(f){
  return f.sort((a,b) => a.ID.length < b.ID.length ? 1 : a.ID.length == b.ID.length ? a.ID < b.ID ? -1 : 1 :-1)
          .reduce((p,c,i,a) => {var parent = !!c.ParentID && a.find(e => e.ID === c.ParentID);
                                !!parent ? !!parent.Sub && parent.Sub.push(c) || (parent.Sub=[c]) : p.push(c);
                                return p;},[]);
};
document.write("<pre>" +  JSON.stringify(nested(flat),null,2) + "</pre>");

OK as per your comment i decided to find a solution to nest a flat array when there is absolutely no information other than parental relationship. I mean the array item properties can be of two type.

[{id: AY998, pid: FT497}, {id: SS113, pid: MN857}, {id: MN857, pid: "root"}, {id: FT497...

where id is the id of the element, pid is the parents id and some objects are root and there is no other information like level etc.

So the idea is to sort the array on parental seniority which means no parent will be listed after it's children. Accordingly once the sort is done a nesting can easily be done by a reverse iteration.

Ok lets create an shuffled array of 100 items of such a nature. (I actually had to create such a code to generate a data array of items with unique id's and proper parental relationship. Lets see the code

var flat = [
      { id: 'KR807', pid: 'UT731' },
      { id: 'DW402', pid: 'root' },
      { id: 'ID042', pid: 'RR203' },
      { id: 'ZT645', pid: 'CP292' },
      { id: 'LD796', pid: 'WI018' },
      { id: 'KH280', pid: 'JO343' },
      { id: 'EC894', pid: 'DX943' },
      { id: 'CR293', pid: 'VT921' },
      { id: 'XI611', pid: 'RQ903' },
      { id: 'YG388', pid: 'VN945' },
      { id: 'ZL243', pid: 'AA689' },
      { id: 'VK295', pid: 'CM110' },
      { id: 'CD374', pid: 'VK295' },
      { id: 'XO588', pid: 'ZL243' },
      { id: 'OM916', pid: 'WI018' },
      { id: 'JQ797', pid: 'CM110' },
      { id: 'BF782', pid: 'root' },
      { id: 'EK012', pid: 'VK295' },
      { id: 'AD556', pid: 'PK567' },
      { id: 'LA463', pid: 'KJ237' },
      { id: 'EL156', pid: 'MT394' },
      { id: 'VE720', pid: 'YG388' },
      { id: 'MT364', pid: 'CD374' },
      { id: 'JO343', pid: 'RJ027' },
      { id: 'QQ957', pid: 'PY806' },
      { id: 'UT731', pid: 'MT394' },
      { id: 'NA571', pid: 'OM916' },
      { id: 'NK641', pid: 'VT921' },
      { id: 'YX336', pid: 'FN157' },
      { id: 'RO244', pid: 'VT921' },
      { id: 'BJ784', pid: 'NA571' },
      { id: 'RJ027', pid: 'NH992' },
      { id: 'ZZ311', pid: 'EE630' },
      { id: 'CK935', pid: 'DX943' },
      { id: 'GF710', pid: 'PY806' },
      { id: 'WZ371', pid: 'MU258' },
      { id: 'IM089', pid: 'GL915' },
      { id: 'GN046', pid: 'NH992' },
      { id: 'MT394', pid: 'root' },
      { id: 'OC487', pid: 'WI018' },
      { id: 'KQ384', pid: 'AD556' },
      { id: 'VZ391', pid: 'ZS119' },
      { id: 'VT921', pid: 'MT394' },
      { id: 'OP416', pid: 'HT085' },
      { id: 'QU319', pid: 'ID042' },
      { id: 'SG270', pid: 'CP292' },
      { id: 'BG562', pid: 'WJ207' },
      { id: 'DX943', pid: 'NK641' },
      { id: 'II920', pid: 'UT731' },
      { id: 'AX150', pid: 'JO343' },
      { id: 'TO181', pid: 'YG388' },
      { id: 'WI985', pid: 'VK295' },
      { id: 'DU020', pid: 'VK225' },
      { id: 'RQ903', pid: 'EL156' },
      { id: 'EP215', pid: 'PK567' },
      { id: 'CZ627', pid: 'PY783' },
      { id: 'MU258', pid: 'GL915' },
      { id: 'MC556', pid: 'XI611' },
      { id: 'XX495', pid: 'II920' },
      { id: 'KJ237', pid: 'YG388' },
      { id: 'CP292', pid: 'UT731' },
      { id: 'MH665', pid: 'EL156' },
      { id: 'VK225', pid: 'FN157' },
      { id: 'FU290', pid: 'AX150' },
      { id: 'EE630', pid: 'GL915' },
      { id: 'VN945', pid: 'root' },
      { id: 'PK567', pid: 'VT921' },
      { id: 'PY806', pid: 'NH992' },
      { id: 'FN157', pid: 'GL915' },
      { id: 'DB935', pid: 'root' },
      { id: 'WK936', pid: 'ZL243' },
      { id: 'PY783', pid: 'WJ207' },
      { id: 'WJ207', pid: 'RO244' },
      { id: 'UR082', pid: 'VT921' },
      { id: 'AR742', pid: 'CD374' },
      { id: 'LS455', pid: 'IM089' },
      { id: 'GH814', pid: 'EL156' },
      { id: 'DX929', pid: 'II920' },
      { id: 'YR376', pid: 'CD374' },
      { id: 'EJ895', pid: 'XO588' },
      { id: 'ND802', pid: 'FU290' },
      { id: 'ZS119', pid: 'GD350' },
      { id: 'GD350', pid: 'YG388' },
      { id: 'HT085', pid: 'GL915' },
      { id: 'RR203', pid: 'AA689' },
      { id: 'IC103', pid: 'KR807' },
      { id: 'XT553', pid: 'WZ371' },
      { id: 'JZ880', pid: 'EL156' },
      { id: 'AA689', pid: 'EP215' },
      { id: 'TJ550', pid: 'RJ027' },
      { id: 'GL915', pid: 'root' },
      { id: 'BI123', pid: 'GD350' },
      { id: 'LD710', pid: 'JZ880' },
      { id: 'MQ351', pid: 'AD556' },
      { id: 'WI018', pid: 'NH992' },
      { id: 'KC160', pid: 'AD556' },
      { id: 'CM110', pid: 'root' },
      { id: 'OK014', pid: 'GH814' },
      { id: 'FD929', pid: 'VK225' },
      { id: 'NH992', pid: 'PK567' }
];

function construct(ar){
  var lut = {},
   sorted = [];
  function sort(a){
  	var len = a.length,
  	    fix = -1;
  	for (var i = 0; i < len; i++ ){
  	  while (!!~(fix = a.findIndex(e => a[i].pid == e.id)) && fix > i)
            [a[i],a[fix]] = [a[fix],a[i]]; // ES6 swap
  	  lut[a[i].id]=i;
  	}console.log(lut); //check LUT on the console.
  	return a;
  }
  sorted = sort(ar.slice(0)); // don't modify things that don't belong to you :)
  for (var i = sorted.length-1; i >= 0; i--){
  	if (sorted[i].pid != "root") {
  	  !!sorted[lut[sorted[i].pid]].children && sorted[lut[sorted[i].pid]].children.push(sorted.splice(i,1)[0])
  	                                        || (sorted[lut[sorted[i].pid]].children = [sorted.splice(i,1)[0]]);
  	}
  }
  return sorted;
}
document.write("<pre>" + JSON.stringify(construct(flat),null,2) + "</pre>");

So it works nice and fast. The key is the sort algorithm. As mentioned before it sorts the array according to the parental seniority and no child can come before it's parent. This is the only condition. But at the same time it prepares a LUT (hash list) of the parent id's indexes so that once we start reverse iterating the array (from last item to first) it avoids us from doing expensive searches for the parent. Instead we will look it's index up from the LUT (look up table) object and inserts it's children if any. Very fast..!

So here is the repl.it for you to play.