Know the depth of a dictionary

Question

Supposing we have this dict:

d = {'a':1, 'b': {'c':{}}}

What would be the most straightforward way of knowing the nesting depth of it?

Answer 1

You need to create a recursive function:

>>> def depth(d):
...     if isinstance(d, dict):
...         return 1 + (max(map(depth, d.values())) if d else 0)
...     return 0
...
>>> d = {'a':1, 'b': {'c':{}}}
>>> depth(d)
3

Answer 2

You'll have to traverse the dictionary. You could do so with a queue; the following should be safe from circular references:

from collections import deque

def depth(d):
    queue = deque([(id(d), d, 1)])
    memo = set()
    while queue:
        id_, o, level = queue.popleft()
        if id_ in memo:
            continue
        memo.add(id_)
        if isinstance(o, dict):
            queue += ((id(v), v, level + 1) for v in o.values())
    return level

Note that because we visit all dictionary values in breath-first order, the level value only ever goes up. The memo set is used to ensure we don't try to traverse a circular reference, endlessly.

Or you could traverse the tree with recursion (which effectively uses function calls as a stack). I've used functools.singledispatch() for easy expansion to other container types:

from functools import singledispatch, wraps

@singledispatch
def depth(_, _level=1, _memo=None):
    return _level

def _protect(f):
    """Protect against circular references"""
    @wraps(f)
    def wrapper(o, _level=1, _memo=None, **kwargs):
        _memo, id_ = _memo or set(), id(o)
        if id_ in _memo: return _level
        _memo.add(id_)
        return f(o, _level=_level, _memo=_memo, **kwargs)
    return wrapper

def _protected_register(cls, func=None, _orig=depth.register):
    """Include the _protect decorator when registering"""
    if func is None and isinstance(cls, type):
        return lambda f: _orig(cls, _protect(f))
    return _orig(cls, _protect(func)) if func is not None else _orig(_protect(cls))
depth.register = _protected_register

@depth.register
def _dict_depth(d: dict, _level=1, **kw):
    return max(depth(v, _level=_level + 1, **kw) for v in d.values())

This is as depth-first search, so now max() is needed to pick the greatest depth for the current object under scrutiny at each level. A dictionary with 3 keys of each different depths should reflect the greatest depth at that level.

The memo set used in either version tracks object ids, so we don't run is circles if you did something like foo = {}; foo["bar"] = foo.

Demo:

>>> d = {'a':1, 'b': {'c':{}}}
>>> depth(d)
3
>>> d = {'foo': {'bar': {'baz': 0}, 'spam': {'ham': {'monty': 1}, 'eric': 'idle'}}, 'john': 'cleese'}
>>> depth(d)
5
>>> circular = {}
>>> circular["self"] = circular
>>> depth(circular)
2

The recursive singledispatch version can be expanded to cover more containers, such as lists:

@depth.register
def _list_depth(l: list, _level=1, **kw):
    return max(depth(v, _level=_level + 1, **kw) for v in l)

Because I've augmented the standard .register decorator to handle circular-reference testing, implementing additional container support is relatively trivial. Just remember to pass along any extra keyword arguments to the recursive call!

Answer 3

A non-recursive solution:

def depth(d):

    depth=0
    q = [(i, depth+1) for i in d.values() if isinstance(i, dict)]
    max_depth = 0
    while (q):
        n, depth = q.pop()
        max_depth = max(max_depth, depth)
        q = q + [(i, depth+1) for i in n.values() if isinstance(i, dict)]

    print max_depth

Answer 4

Iterative solution:

from collections import deque


def depth(d):
    q = deque([d])
    q2 = deque()
    max_depth = 0
    while q:
        curr_dict = q.popleft()
        if isinstance(curr_dict, dict):
            for di in curr_dict.itervalues():
                q2.append(di)
        if not q:
            q, q2 = q2, q
            max_depth += 1
    return max_depth

print depth(None)
print depth({})
print depth({"a": "b"})
print depth({"a": "b", "c": {"d": "e"}, "f": {"g": "h"}, "i": {"j": "k"}, "x": {}, "z": {} })
print depth({'a':1, 'b': {'c':{}}})
print depth({'foo': {'bar': {'baz': 0}, 'spam': {'ham': {'monty': 1}, 'eric': 'idle'}}, 'john': 'cleese'})