Find depth of object in iterative way

user_2652759 0
Viewed 282

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

ecmascript-6 algorithm javascript
3 Answers

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

user_38746230

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

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

user_98674510
Related