Recursive depth of python dictionary

Question

G'day,

I am trying to find the recursive depth of a function that trawls a dictionary and I'm a bit lost... Currently I have something like:

myDict = {'leve1_key1': {'level2_key1': {'level3_key1': {'level4_key_1': {'level5_key1':   'level5_value1'}}}}}

And I want to know just how nested the most nested dictionary is... so I do the following...

def dict_depth(d, depth):

    for i in d.keys():
        if type(d[i]) is dict:
            newDict = d[i]
            dict_depth(newDict, depth+1)
    return depth

print dict_depth(myDict, 0)

Only problem is, the recursive loop only returns the return of the final value (0). if I put in a print statement for i in d.keys(): then I can at least print the highest value of recursion, but returning the value is a different matter...

I'm sure this is straightforward - I've just got jellybrain.

You will not find any limit here (except for available memory). Every nested dictionary is a new object which knows nothing about its parent. — usr, Mar 02 '12 at 19:24
But your code might run into a stack-overflow. This has nothing to do with any dictionary limits. — usr, Mar 02 '12 at 19:25

Raymond Hettinger · Accepted Answer · 2012-03-02T19:53:12.477

11

Be sure to assign the result of the recursive call to depth. Also, as @amit says, consider using max so that you can handle dicts with multiple key value pairs (a treelike structure).

def dict_depth(d, depth=0):
    if not isinstance(d, dict) or not d:
        return depth
    return max(dict_depth(v, depth+1) for k, v in d.iteritems())

>>> myDict = {'leve1_key1': {'level2_key1': 
               {'level3_key1': {'level4_key_1': 
                  {'level5_key1':   'level5_value1'}}}}}
>>> dict_depth(myDict)
5

edited Mar 02 '12 at 19:53

answered Mar 02 '12 at 19:04

Raymond Hettinger

216,523
63
388
485

1

just note that without using `max()` on depth, you might override `depth` with a smaller value, if the dictionary has more then 1 key. – amit Mar 02 '12 at 19:10
@amit I agree. It's always hazardous to start with the OP's code :-) – Raymond Hettinger Mar 02 '12 at 19:45

score 2 · Answer 2 · edited Jan 09 '15 at 08:16

MyDict = {'a': {'a1': {'a11': 5, 'a12':[{2:'a22'}], 'a13':{'a14':'a11'}}, 'a2': 6}, 'b':{7:{8:{9:{10:{11:'11'}}}}}, 'c': {'c1': 18, 'c2': 1}}

def find_depth(dep,val):
    if isinstance(val,dict):
        dep=dep+1
        for j in val:
            find_depth(dep,val[j])
        temp_depth.append(dep)
        dep=0
        return max(temp_depth)
    elif isinstance(val,list):
        for k in val:
            find_depth(dep,k)


max_depth={}
for i in MyDict:
    dep=0
    temp_depth=[]
    max_depth.update({i:(find_depth(dep,MyDict[i]))})
    print max_depth

Here is code works fine if even list also included.

score 2 · Answer 3 · answered Mar 02 '12 at 19:03

You should store the value retured from the recursive call, and return the max value found, otherwise - you are calling the recursive function without doing anything with the returned value! [and returning 0 as expected, since it was never changed]

def dict_depth(d, depth):
    ret = depth 
    for i in d.keys():
        if type(d[i]) is dict:
            newDict = d[i]
            ret = max(dict_depth(newDict, depth+1),ret) #finding max and storing it
    return ret #returning the max found

@RaymondHettinger: Works perfectly for me and prints '4'. I assumed here the OP wanted the outer dictionary as "0". — amit, Mar 02 '12 at 19:17

score 0 · Answer 4 · answered May 06 '14 at 17:07

A non-recursive version:

def depth(d):

    depth=0
    q = [(i, depth+1) for i in d.values() if isinstance(i, dict)]
    max_depth = 0
    while (q):
        print 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

score 0 · Answer 5 · answered Mar 02 '12 at 19:29

I can't possible beat Raymond Hettinger, if he is THE R.H. ;-) But i came to a similar solution with some print statements to illustrate what's happening!

d = {1: 2, 2: {3: {5: 6}}, 3: {4: 4}, 7: 8}
def recursion_depth(dict_, depth):
    for k in dict_:
        print "key{0}:value{1} = depth:{2}".format(k, dict_[k], depth)
    if type(dict_[k]) == dict:
        actual_depth = recursion_depth(dict_[k], depth+1)
        if actual_depth > depth: depth += 1
    return depth

>>>recursion_depth(d,0)
key1:value2 = depth:0
key2:value{3: {5: 6}} = depth:0
key3:value{5: 6} = depth:1
key5:value6 = depth:2
key3:value{4: 4} = depth:1
key4:value4 = depth:2
key7:value8 = depth:2
2

Recursive depth of python dictionary

5 Answers5

Linked

Related