4

I am writing a function for calculating the depth of an object.

Here is my recursive version which seems to work as expected:

function findDepth(obj, firstCall = true) {
  if (firstCall && typeof obj !== "object") {
    return -1;
  }
  return Object.keys(obj).reduce((max, k) => {
    if (typeof obj[k] === "object" && obj[k] !== null) {
      const val = findDepth(obj[k], false) + 1;
      if (val > max) {
        max = val;
      }
    }
    return max;
  }, 1);
}

const input1 = {
  a: {
    b: "test",
    c: {
      d: {
        e: {
          f: [1, 2, 3],
          g: {
            a: null,
            z: {
              d: "casdsadasdsa",
              q: {
                z: {
                  i: undefined
                }
              }
            }
          }
        }
      },
      c: {
        a: "sad"
      }
    },
    d: {
      e: 5
    }
  },
  b: {
    c: {
      d: "dsada"
    }
  }
};

const input2 = {
  w: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk",
        q: {
          w: {
            z: "dsajkdasjdla"
          }
        }
      },
      h: "dsiaodsiad"
    }
  },
  a: "test",
  b: "test2",
  c: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk"
      },
      h: "dsiaodsiad"
    }
  },
  e: "bye"
};

console.log(findDepth(input1));
console.log(findDepth(input2));

Now I am trying to write an iterative version, but I cannot find the best way to make the loop work. 

function findDepthIterative(obj) {
  if (typeof obj !== "object") {
    return -1;
  }
  let max = 1;
  let copy = Object.assign({}, obj);
  let keys = Object.keys(copy);
  while (keys.length) {
    if (typeof copy[keys[0]] !== "object" && copy[keys[0]] !== null) {
      delete copy[keys[0]];
      keys = Object.keys(copy);
    } else {
      max++;
      copy = Object.assign({}, copy[keys[0]]);
      keys = Object.keys(copy);
    }
  }
  return max;
}

const input1 = {
  a: {
    b: "test",
    c: {
      d: {
        e: {
          f: [1, 2, 3],
          g: {
            a: null,
            z: {
              d: "casdsadasdsa",
              q: {
                z: {
                  i: undefined
                }
              }
            }
          }
        }
      },
      c: {
        a: "sad"
      }
    },
    d: {
      e: 5
    }
  },
  b: {
    c: {
      d: "dsada"
    }
  }
};

const input2 = {
  w: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk",
        q: {
          w: {
            z: "dsajkdasjdla"
          }
        }
      },
      h: "dsiaodsiad"
    }
  },
  a: "test",
  b: "test2",
  c: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk"
      },
      h: "dsiaodsiad"
    }
  },
  e: "bye"
};

console.log(findDepthIterative(input1));
console.log(findDepthIterative(input2));

As you can see from the output and the code, it just takes the first property inside the loop:

while (keys.length) {
    if (typeof copy[keys[0]] !== "object" && copy[keys[0]] !== null) {
      delete copy[keys[0]];
      keys = Object.keys(copy);
    } else {
      max++;
      copy = Object.assign({}, copy[keys[0]]);
      keys = Object.keys(copy);
    }
  }

The idea was to delete the property each iteration, but I am not getting in the right way. I tried to change it with copy[keys[keys.length - 1]] but in this way it takes only the last property instead. Actually the issue is how to loop over all the keys, on all the depth levels, as in the recursive version.

Any suggestion about how to implement this algorithm in an iterative way?

Even any suggestion on how to improve the recursive one (or if I am missing something) is more than welcome.

p.s. NO LOADASH, UNDERSCORE, RAMDA, or whatever. Just Vanilla JS

Improve this question

3 Answers 3

Reset to default
5

You just need to keep a stack and push children into it while keeping track of the current depth. You can keep track of that by pushing an array of [depth, obj] into the stack and then when you pop() add one to the depth before pushing children.

const input1  = {w: {d: "hello",f: {g: "dsadas",z: {b: "dsajkdasjldk",q: {w: {z: "dsajkdasjdla"}}},h: "dsiaodsiad"}},a: "test",b: "test2",c: {d: "hello",f: {g: "dsadas",z: {b: "dsajkdasjldk"},h: "dsiaodsiad"}},e: "bye"};
  
  
function findDepthIterative(obj) {
    if (typeof obj !== "object") {
      return -1;
    }
    let max = 0;
    // current depth, children
    let stack = [[0, Object.values(obj)]];
    
    while(stack.length){
        let [depth, cur] = stack.pop()
        if (depth > max) max = depth

        if (typeof cur === "object" && cur !== null){
            Object.values(cur).forEach(c => stack.push([depth+1, c]))     
        }
    }
    return max
  }
  

console.log(findDepthIterative(input1))

// sanity check:
const depth0 = {}
const depth1 = {a:1}
const depth2 = {a:{b:2}}

console.log(findDepthIterative(depth0))
console.log(findDepthIterative(depth1))
console.log(findDepthIterative(depth2))

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

sorry my bad I deleted the comment, there was a typeof, even the not strict equal was fine :) sorry again
That's okay === is better.
@quirimmo brilliant? I posted the exact same algorithm a minute before. No disrespect to your eloquent answer, Mark Meyer. +1 from me.
@גלעדברקן why are you taking it so badly? I am going through your solution too just give me the time to do it
@quirimmo I must've had a bad day, ha ha. Sorry about that.
|
2

One way to iterate could be a depth first search using a stack.

function f(obj){
  let stack = Object.keys(obj).map(k => [obj[k], 1]);
  let max = 0;

  while (stack.length){
    let [maybeObj, d] = stack.pop();
    max = Math.max(max, d);
    if (typeof maybeObj == 'object' && maybeObj !== null)
      Object.keys(maybeObj).map(k =>
        stack.push([maybeObj[k], d + 1]));
  }

  return max;
}

We could also make the recursion slightly more succinct:

function f(obj){
  if (typeof obj !== 'object' || obj === null)
    return 0;

  return Object.keys(obj).reduce((acc, k) => 
    Math.max(acc, 1 + f(obj[k])), 0);
}
Improve this answer

5 Comments

Heh, or as Mark Meyer suggested, use Object.values.
your k is undefined inside the while, it just exists inside the first map function
@quirimmo this answer does not seem to be appreciated, typos notwithstanding.
For now, you'll have to live with my mistake. (This answer has the same algorithm as Mark Meyer's. Go figure.)
brilliant thanks a million, and thanks also for the syntactic sugar of the recursive version :) Great!
2

You should use an array instead of the object which won't work properly if there are duplicate keys. The array should contain all the objects that occur at a certain level. For each iteration, you map the array into a new one containing the previous objects' direct children:

function findDepthIterative(obj) {
  if (typeof obj !== "object") {
    return -1;
  }

  let arr = [obj];                                          // the array containing the objects that occur at a certain level, initially contains obj being the only object at the first level
  let levels = 0;                                           // levels counter

  do {                                                      // keep doing this
    levels++;                                               // increment the levels counter

    let newArr = [];                                        // make a new array for the next level
    arr.forEach(obj => {                                    // populate it with the old level objects' children
      for(let key in obj) {
        if(obj[key] && typeof obj[key] === "object") {
          newArr.push(obj[key]);
        }
      }
    });
    arr = newArr;                                          // make arr the new array of object (next level)
  } while (arr.length);                                    // while there are still levels with objects in them

  return levels;
}

Demo:

function findDepthIterative(obj) {
  if (typeof obj !== "object") {
    return -1;
  }

  let arr = [obj];
  let levels = 0;

  do {
    levels++;
    
    let newArr = [];
    arr.forEach(obj => {
      for(let key in obj) {
        if(obj[key] && typeof obj[key] === "object") {
          newArr.push(obj[key]);
        }
      }
    });
    arr = newArr;
  } while (arr.length);

  return levels;
}

const input1 = {
  a: {
    b: "test",
    c: {
      d: {
        e: {
          f: [1, 2, 3],
          g: {
            a: null,
            z: {
              d: "casdsadasdsa",
              q: {
                z: {
                  i: undefined
                }
              }
            }
          }
        }
      },
      c: {
        a: "sad"
      }
    },
    d: {
      e: 5
    }
  },
  b: {
    c: {
      d: "dsada"
    }
  }
};

const input2 = {
  w: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk",
        q: {
          w: {
            z: "dsajkdasjdla"
          }
        }
      },
      h: "dsiaodsiad"
    }
  },
  a: "test",
  b: "test2",
  c: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk"
      },
      h: "dsiaodsiad"
    }
  },
  e: "bye"
};

console.log(findDepthIterative(input1));
console.log(findDepthIterative(input2));

Improve this answer

1 Comment

thanks a lot! makes absolutely sense. Maybe I just prefer the solution with the stack, even if the logic is pretty the same. Thanks again :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.