Finding a key recursively in a dictionary

Question

I'm trying to write a very simple function to recursively search through a possibly nested (in the most extreme cases ten levels deep) Python dictionary and return the first value it finds from the given key.

I cannot understand why my code doesn't work for nested dictionaries.

def _finditem(obj, key):     if key in obj: return obj[key]     for k, v in obj.items():         if isinstance(v,dict):             _finditem(v, key)  print _finditem({"B":{"A":2}},"A") 

It returns None.

It does work, however, for _finditem({"B":1,"A":2},"A"), returning 2.

I'm sure it's a simple mistake but I cannot find it. I feel like there already might be something for this in the standard library or collections, but I can't find that either.

Answer 1

when you recurse, you need to return the result of _finditem

def _finditem(obj, key):     if key in obj: return obj[key]     for k, v in obj.items():         if isinstance(v,dict):             return _finditem(v, key)  #added return statement 

To fix the actual algorithm, you need to realize that _finditem returns None if it didn't find anything, so you need to check that explicitly to prevent an early return:

def _finditem(obj, key):     if key in obj: return obj[key]     for k, v in obj.items():         if isinstance(v,dict):             item = _finditem(v, key)             if item is not None:                 return item 

Of course, that will fail if you have None values in any of your dictionaries. In that case, you could set up a sentinel object() for this function and return that in the case that you don't find anything -- Then you can check against the sentinel to know if you found something or not.

Answer 2

Here's a function that searches a dictionary that contains both nested dictionaries and lists. It creates a list of the values of the results.

def get_recursively(search_dict, field):     """     Takes a dict with nested lists and dicts,     and searches all dicts for a key of the field     provided.     """     fields_found = []      for key, value in search_dict.iteritems():          if key == field:             fields_found.append(value)          elif isinstance(value, dict):             results = get_recursively(value, field)             for result in results:                 fields_found.append(result)          elif isinstance(value, list):             for item in value:                 if isinstance(item, dict):                     more_results = get_recursively(item, field)                     for another_result in more_results:                         fields_found.append(another_result)      return fields_found