CODEWITHSUNDEEP
javascriptalgorithmdata-structurestreebreadth-first-search
Ying
Ying

Reputation: 299

Maximum Depth of N-ary Tree when use BFS

For get the max depth of a nary-tree, this code below is a correct answer.

var maxDepth = function(root) {
 if (!root) {
    return 0
 }
 let depth = 0;
 let arr=[root];

 while (arr.length) {
    let arrlength=arr.length;
    for (let i=0;i<arrlength;i++) {
        let curr=arr.shift();
        arr.push(...curr.children);           
    }
    depth++;
 }
 return depth;

};

However, if I use arr.length in the for loop instead of use "let arrlength=arr.length;" and use arrlength, it will be a wrong answer... May I know why? I can't tell any difference. Thank you so much!

var maxDepth = function(root) {
 if (!root) {
    return 0
 }
 let depth = 0;
 let arr=[root];

 while (arr.length) {       
    for (let i=0;i<arr.length;i++) {
        let curr=arr.shift();
        arr.push(...curr.children);           
    }
    depth++;
 }
 return depth;

};

can be tested here: https://leetcode.com/problems/maximum-depth-of-n-ary-tree/

Upvotes: 0

Views: 157

Answers (1)

Barmar
Barmar

Reputation: 780889

let curr = arr.shift() removes the first element from the array and assigns it to curr.

arr.push(...curr.children) adds all the children to the end of the array.

Both of these operations change the array length, and the test i < arr.length uses the current length each time through. But the loop is only supposed to process the original array elements. arrlength contains the array's original length before the loop. It won't change as the array is modified, so the loop will operate the correct number of times.

You could use .length in the loop if you made a copy of arr before the loop, and looped over that rather than modifying the array you're looping over.

var maxDepth = function(root) {
  if (!root) {
    return 0
  }
  let depth = 0;
  let arr = [root];

  while (arr.length) {
    let copy = [...arr];
    arr.splice(0, arr.length);
    for (let i = 0; i < copy.length; i++) {
      let curr = copy[i];
      arr.push(...curr.children);
    }
    depth++;
  }
  return depth;

};

const tree = {
  value: 1,
  children: [{
      value: 3,
      children: [{
        value: 5,
        children: []
      }, {
        value: 6,
        children: []
      }]
    },
    {
      value: 2,
      children: []
    },
    {
      value: 3,
      children: []
    }
  ]
};

console.log(maxDepth(tree));

Upvotes: 2

Related Questions