Find a key inside a deeply nested dictionary

Question

I have a lot of nested dictionaries, I am trying to find a certain key nested inside somewhere.

e.g. this key is called "fruit". How do I find the value of this key?

Answer 1

@Håvard's recursive solution is probably going to be OK... unless the level of nesting is too high, and then you get a RuntimeError: maximum recursion depth exceeded. To remedy that, you can use the usual technique for recursion removal: keep your own stack of items to examine (as a list that's under your control). I.e.:

def find_key_nonrecursive(adict, key):
  stack = [adict]
  while stack:
    d = stack.pop()
    if key in d:
      return d[key]
    for k, v in d.iteritems():
      if isinstance(v, dict):
        stack.append(v)

The logic here is quite close to the recursive answer (except for checking for dict in the right way;-), with the obvious exception that the recursive calls are replaced with a while loop and .pop and .append operations on the explicit-stack list, stack.

Answer 2

Almost 11 years later... based on Alex Martelli answer with slight modification, for Python 3 and lists:

def find_key_nonrecursive(adict, key):
    stack = [adict]
    while stack:
        d = stack.pop()
        if key in d:
            return d[key]
        for v in d.values():
            if isinstance(v, dict):
                stack.append(v)
            if isinstance(v, list):
                stack += v