Counting the highest level of nested Arrays inside Object

Question

I have a problem with a task, I have to count the highest level in a structure which looks like this:

let node = {
    age: 23,
    name: "christian",
    children: [{
        age: 25,
        name: "michael",
        children: [{
            age: 33,
            name: "Johann",
            children: [{
                age: 45,
                name: "Christiaaann",
            }]
        }]
    }, {
        age: 90,
        name: "Monika",
        children: [{
            age: 10,
            name: "WHATEVER",
        }]
    }]
};

The level of the first subtree would be 3 as it contains 3 nested children arrays. The right level would be 2 as it contains 2 nested children arrays.

I tried to solve it recursively, and of course I know that I have to count the level of each subtree and then check it with a condition if it is greater than the previous maximum.

My problem is that I don't know where to count it up in the recursive call.

This is my solution, so far

let node = {
    age: 23,
    name: "christian",
    children: [{
        age: 25,
        name: "michael",
        children: [{
            age: 33,
            name: "Johann",
            children: [{
                age: 45,
                name: "Christiaaann",
            }]
        }]
    }, {
        age: 90,
        name: "Monika",
        children: [{
            age: 10,
            name: "WHATEVER",
        }]
    }]

};

let level_count;
let max_count = 0;

function level_counter(obj, func) {
    level_count = 0;
    func(obj);
    console.log("INSIDEFUNCTION", level_count);


    if (obj.children) {
        level_count++;
        obj.children.forEach(function(child) {
            console.log(child);
            level_counter(child, func);


        });
        if (level_count > max_count) {
            max_count = level_count;
        }
    }
}

function tree_get_levels(root) {
    level_counter(root, function(obj) { });
    console.log("DOWNONE", level_count);
    return 0;
}

let result = tree_get_levels(node);
console.log(result);

it's not clear to me what is: ״the highest lvl in a structure״? — Nir Alfasi
– Nir Alfasi, Commented Sep 12, 2022 at 10:07
What do you mean by "highest level"? Do you mean the highest (largest) depth? What is the answer for the structure you've provided? (I could argue it various ways, depending on what you mean, but 3 or 4 seems likely.) — T.J. Crowder
– T.J. Crowder, Commented Sep 12, 2022 at 10:08
in this example from above left side would be 3 as it has 3 children arrays and the right side would be 2 — Aalexander
– Aalexander, Commented Sep 12, 2022 at 10:08

T.J. Crowder · Accepted Answer · 2022-09-12 10:27:27Z

I tried to solve it recursively, and of course I know that I have to count the level of each subtree and then check it with a condition if it is greater than the previous maximum.

My problem is that I don't know where to count it up in the recursive call.

You need to use the return value of the recursive call, adding one for the level making the call to it. Separately, always avoid global variables when you're trying to write a recursive solution; every level of recursion sees the same values for those variables, and assigning to them won't work correctly. Stick to variables defined within the recursive function, and (again) report values back up the stack by returning them.

See inline notes in the code:

let node = {
    age: 23,
    name: "christian",
    children: [{
        age: 25,
        name: "michael",
        children: [{
            age: 33,
            name: "Johann",
            children: [{
                age: 45,
                name: "Christiaaann",
            }]
        }]
    }, {
        age: 90,
        name: "Monika",
        children: [{
            age: 10,
            name: "WHATEVER",
        }]
    }]
};

function countLevels(obj, func) {
    // No levels so far
    let levelCount = 0;
    func(obj); // Not sure what this function is for

    // If there are any children...
    if (obj.children) {
        // There are, so we've already gone one level down
        for (const child of obj.children) {
            // Get levels starting at this child, then add one because we've
            // already gone one level down
            const levelsFromChild = countLevels(child, func) + 1;
            // Remember it if it's higher than the maximum we've seen
            if (levelCount < levelsFromChild) {
                levelCount = levelsFromChild;
            }
            // Or that could be replaced with:
            // levelCount = Math.max(levelCount, countLevels(child, func) + 1);
        }
    }
    // I added this so you could see the levels count starting from each object
    console.log(`${levelCount} level(s) from ${JSON.stringify(obj)}`);
    // Return the levels found from this object
    return levelCount;
}

// No need for a separate wrapper function, just call the counter directly
let result = countLevels(node, function func(obj) { });
console.log(`Deepest: ${result}`);

.as-console-wrapper {
    max-height: 100% !important;
}

Great solution, thanks a lot. I guess I should study recursion again :D

Nanang Mahdaen El-Agung · Accepted Answer · 2022-09-12 10:41:20Z

0

You can try this:


function highestDepth(obj) {
  let depth = 0;

  if (Array.isArray(obj.children) && obj.children.length) {
    depth += 1;

    let subDepth = 0;
    for (const child of obj.children) {
      subDepth = Math.max(subDepth, highestDepth(child));
    }

    depth += subDepth;
  }

  return depth;
}

console.log(highestDepth(node));

answered Sep 12, 2022 at 10:41

Nanang Mahdaen El-Agung

1,42410 silver badges14 bronze badges

Comments

Scott Sauyet · Accepted Answer · 2022-09-12 14:32:18Z

A simple recursive version first checks whether the node has children. If it doesn't, we simply return 0; if it does, we recur over each of its children, and take the maximum of those (or 0 if the children array is empty) and add 1. It looks like this:

const maxDepth = (node) => 'children' in node 
  ? 1 + Math .max (0, ... node .children .map (maxDepth)) 
  : 0

const node = {age: 23, name: "christian", children: [{age: 25, name: "michael", children: [{age: 33, name: "Johann", children: [{age: 45, name: "Christiaaann"}]}]}, {age: 90, name: "Monika", children: [{age: 10, name: "WHATEVER"}]}]}

console .log (maxDepth (node))

The 0 passed as the first parameter to Math .max is necessary because Math .max () (with no parameters) returns -Infinity. It's an interesting exercise to try to figure out why that is.

vincent · Accepted Answer · 2022-09-22 04:07:30Z

0

Here is an iterative solution using object-scan. This solution will work even when you are dealing with very deeply nested object hierarchies.

.as-console-wrapper {max-height: 100% !important; top: 0}

<script type="module">
import objectScan from 'https://cdn.jsdelivr.net/npm/[email protected]/lib/index.min.js';

const node = { age: 23, name: 'christian', children: [{ age: 25, name: 'michael', children: [{ age: 33, name: 'Johann', children: [{ age: 45, name: 'Christiaaann' }] }] }, { age: 90, name: 'Monika', children: [{ age: 10, name: 'WHATEVER' }] }] };

const fn = objectScan(['**{children[*]}'], {
  rtn: 'count', // for performance
  beforeFn: (state) => {
    state.context = { depth: 0 };
  },
  filterFn: ({ context, depth }) => {
    context.depth = Math.max(context.depth, depth);
  },
  afterFn: ({ context }) => context.depth / 2
});

console.log(fn(node));
// => 3
</script>

Disclaimer: I'm the author of object-scan

answered Sep 22, 2022 at 4:07

vincent

2,1893 gold badges19 silver badges30 bronze badges

2 Comments

Scott Sauyet Over a year ago

But of course, if you're dealing with hierarchies too deeply nested for modern JS engines' recursion limits, this is the least of your problems! :-)

vincent Over a year ago

Hah, fair enough =)

Collectives™ on Stack Overflow

Counting the highest level of nested Arrays inside Object

4 Answers 4

1 Comment

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related