Find depth of object in iterative way

Question

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

Answer 1

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))

Answer 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);
}