CODEWITHSUNDEEP
javascriptjsontypescriptrecursion
tom
tom

Reputation: 2357

Getting the depth of a tree data structure in a simpler way

I have a JSON-like hierarchy of JS objects in the following format:

[
  {
    subs: [ ...other objects... ]
  },
  ...other objects...
]

I wrote a method that returns the number of levels of such a hierarchy:

/* Returns the depth of the tree. */
public getDepth(): number {

  function f(obj: object): number {
    let depth = 0;
    if (obj['subs'].length > 0) {
      obj['subs'].forEach((s: object) => {
        const tempDepth = f(s);
        if (tempDepth > depth) depth = tempDepth;
      });
    }
    return depth + 1;
  }

  if (this.tree.length > 0)
    return Math.max(...this.tree.map((s: object) => f(s)));
  else return 0;

}

It works but it's too complicated. Then, I've found this, much cleaner code: https://stackoverflow.com/a/16075976/5214911

The only difference is that I have not one base object but an array of objects as root. How could I simplify the code to spare that extra if and iteration?

Example data:

const data1 = []; // depth: 0

const data2 = [{}, {}, {}]; // depth: 1

const data3 = [{}, // depth: 5
  {
    "subs": [{
      "subs": [{
        "subs": [{}]
      }, {
        "subs": [{
          "subs": [{}]
        }]
      }]
    }, {
      "subs": [{
        "subs": [{}]
      }]
    }]
  },
  {}
];

Upvotes: 4

Views: 3466

Answers (2)

Nina Scholz
Nina Scholz

Reputation: 386680

You could map the depth of every children and take the maximum value of it.

function getDepth(array) {
    return 1 + Math.max(0, ...array.map(({ subs = [] }) => getDepth(subs)));
}

const
    data1 = [],
    data2 = [{}, {}, {}],
    data3 = [{}, { subs: [{ subs: [{ subs: [{}] }, { subs: [{ subs: [{}] }] }] }, { subs: [{ subs: [{}] }] }] }, {}];

console.log(getDepth(data1) - 1); // 0
console.log(getDepth(data2) - 1); // 1
console.log(getDepth(data3) - 1); // 5

Upvotes: 9

Maheer Ali
Maheer Ali

Reputation: 36584

Use Array.prototype.map() to change each item of array to its length and then use Math.max() on array

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
}
let arr = [...];
let depths = arr.map(x => getDepth(x))
let maxDepth = Math.max(...depths)

Upvotes: 2

Related Questions