How to get the total depth of an unknown JSON hierarchy?

Question

I've been struggling to find/build a recursive function to parse this JSON file and get the total depth of its children.

The file looks something like this:

var input = {
    "name": "positive",
    "children": [{
        "name": "product service",
        "children": [{
            "name": "price",
            "children": [{
                "name": "cost",
                "size": 8
            }]
        }, {
            "name": "quality",
            "children": [{
                "name": "messaging",
                "size": 4
            }]
        }]
    }, {
        "name": "customer service",
        "children": [{
            "name": "Personnel",
            "children": [{
                "name": "CEO",
                "size": 7
            }]
        }]
    }, {
        "name": "product",
        "children": [{
            "name": "Apple",
            "children": [{
                "name": "iPhone 4",
                "size": 10
            }]
        }]
    }] 
}

Solution 1

You can use a recursive function to go through the whole tree:

getDepth = function (obj) {
    var depth = 0;
    if (obj.children) {
        obj.children.forEach(function (d) {
            var tmpDepth = getDepth(d)
            if (tmpDepth > depth) {
                depth = tmpDepth
            }
        })
    }
    return 1 + depth
}

The function works as follow:

• If the object is not a leaf (i.e the object has the children attribute), then:
  • Compute the depth of each child, save the maximal one
  • return 1 + the depth of the deepest child
• Otherwise, return 1

jsFiddle: http://jsfiddle.net/chrisJamesC/hFTN8/

EDIT With modern JavaScript, the function could look like this:

const getDepth = ({ children }) => 1 +
    (children ? Math.max(...children.map(getDepth)) : 0)

jsFiddle: http://jsfiddle.net/chrisJamesC/hFTN8/59/

Solution 2

This will count the number of "leaves" in a tree:

var treeCount = function (branch) {
    if (!branch.children) {
        return 1;
    }
    return branch.children.reduce(function (c, b) {
        return c + treeCount(b);
    }, 0)
}

And an alternative way to get depth:

var depthCount = function (branch) {
    if (!branch.children) {
        return 1;
    }
    return 1 + d3.max(branch.children.map(depthCount));
 }

Comments

[Christopher Chiche]

Do you mean if(!branch.children)?

[Juha Untinen]

How could this be used to get the depth of a literally unknown JSON, or to make it reusable for any kind of JSON? I presume this requires the JSON elements to be called "children", and it will not work if they are eg. "cars" instead of "children", or when one JSON has "flies" and the other has "birds".

[Ali Bahrami]

const gives me TypeError: Cannot match against 'undefined' or 'null'.

[Christopher Chiche]

This is because your JavaScript engine doesn't support new versions of the JavaScript language (ES6+). So you can just use the first version of the script I wrote which does the same.

[user51462]

Thank you for sharing your solution, @ChristopherChiche. I'm curious to know the thought process behind writing the function as I'm struggling to get my head around how it works, especially if I try to think about what value it's returning at each recursion. However, the final value of 4 makes sense if I calculate the return value at each level starting from the leaves/deepest level and working outwards. Is this how you thought about it too?

[Christopher Chiche]

@user51462 It's great that you're willing to learn more! This is a tail recursion, which is quite powerful when working on trees/graphs or other data structures.

[user51462]

@ChristopherChiche, I hadn't heard of tail recursion before, down the recursion rabbit hole I go lol thank you for your help :)