Recursion in hierarchical tree

Question

I am tying to iterate through a hierarchical tree in javascript to determine how many levels it has. Here is a short snippet of my tree:

parent: [
   { id: 1 }
   {
       child1: [
           { id: 2 }
           {
               child2: [
                   { id: 3 }
                   {}
               ]
           }
       ],
       child3: [
           { id: 4 }
           { 
               child4: [
                   { id: 5 }
                   {}
               ],
               child5: [
                   { id: 6 }
                   {
                       child6: [
                           { id: 7 }
                           {}
                       ]
                   }
               ]
           }
       ]
   }
]

There will be an unknown number of parents and children. There is 1 certainty:

• Each element (e.g. parent) ALWAYS has 2 objects in it's array. 1st object is always an ID. 2nd object contains the children it has. This may be empty or populated

My goal is to determine the number of levels that the tree has. For example, there are 4 levels in this example tree (parent = 1, child1 + child3 are on the same level (2), child4 and child5 are on the same level (3) and child6 = 4).

This is my code so far:

for (var j in dependencyTree) {
    if (getObjectSize(dependencyTree[j][1]) > 0) {
        levelsArray.push(j + ': ' + recursiveFunction(dependencyTree[j][1], 1));
    }
}


function recursiveFunction(obj, lvls) {
    if (getObjectSize(obj) > 0) {
        for (var i in obj) {
            recursiveFunction(obj[i][1], lvls++);
        }
    }
    return lvls;
}

getObjectSize() just returns the size of the object. I.e. how many direct children it has. For example, object parent will return 2 (child1 and child3).

In the beginning, the top level parent children are passed into the function.

I think my problem is that for loop (for (var i in obj)) because that may grab the first child parent has (child1) and will eventually return the number of levels that child1 has even though child3 has more.

Any help appreciated.

(Have not yet attempted lodash but have been told it offers no recursive help)

EDIT

{
    "Mobile": [
        {
            "id": 89
        },
        { 
            "Mobile Client": [
                {
                    "id": 100 
                },
                {}
            ]
        }
    ],
    "Service Platform": [
        {
            "id": 90
        },
        {
            "Service Platform": [
                {..."

EDIT (new proposed format):

I have talked with my colleague, the new proposed data format is:

[
    {
        "name": "Mobile",
        "id": 89,
        "children": [
            {
                "name": "Mobile Client",
                "id": 100,
                "children": {}
            }
        ]
    }
];

This seems like much more workable data and will be implemented tomorrow

Answer 1

here is some sample code to give you an idea how to traverse the data - the information is visible through console.

var a = [
   { id: 1 },
   {
   child1: [
       { id: 2 },
       {
           child2: [
               { id: 3 },
               {}
           ]
       }
   ],
   child3: [
       { id: 4 },
       { 
           child4: [
               { id: 5 },
               {}
           ],
           child5: [
               { id: 6 },
               {
                   child6: [
                       { id: 7 },
                       {}
                   ]
               }
           ]
       }
   ]
   }
];

var getNumChildren=function(obj){
  var a = 0;
  if(obj[1]){
for (var key in obj[1]) {
  a++;
  var res = getNumChildren(obj[1][key]);
  console.log(res,a);
  a += res;
}
  }
  return a;
}


console.log(getNumChildren(a));

as far as formatting the data goes, this format might make more sense and be easier to understand and use

[
  {"id":1,
    "children":[
      {"id":2,"children":[
        {"id":4,"children":[]},
        {"id":5,"children":[]}
      ]},
      {"id":3,"children":[]}
    ]
  }
]

---

edit

if you update the data format, you can use this code.

var data =[
  {"id":1,
    "children":[
      {"id":2,"children":[
        {"id":4,"children":[]},
        {"id":5,"children":[]}
      ]},
      {"id":3,"children":[]}
    ]
  },
  {"id":6,"children":[]}
]

var getNumChildren=function(ca){
  var n = ca.length;
  ca.map(function(c){n += getNumChildren(c.children);})
  return n
}

document.write("result: " + getNumChildren(data));

Answer 2

Despite the format, this solution iterates over all elements in arrays as well as in objecs and count them.

function count(array) {
    var c = 0;
    array.forEach(function (a) {
        c++;
        if (typeof a === 'object') {
            Object.keys(a).forEach(function (k) {
                if (Array.isArray(a[k])) {
                    c += count(a[k]);
                }
            });
        }
    });
    return c;
}

var parent = [{ id: 1 }, { child1: [{ id: 2 }, { child2: [{ id: 3 }, {}, ] }], child3: [{ id: 4 }, { child4: [{ id: 5 }, {}], child5: [{ id: 6 }, { child6: [{ id: 7 }, {}] }] }] }],
    newFormat = [{ "name": "Mobile", "id": 89, "children": [{ "name": "Mobile Client", "id": 100, "children": {} }] }];

document.write('<pre>' + JSON.stringify(count(parent), 0, 4) + '</pre>');
document.write('<pre>' + JSON.stringify(parent, 0, 4) + '</pre><hr>');
document.write('<pre>' + JSON.stringify(count(newFormat), 0, 4) + '</pre>');
document.write('<pre>' + JSON.stringify(newFormat, 0, 4) + '</pre>');