python - Finding a key recursively in a dictionary

39
votes

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.

6
pythonsearchrecursiondictionary
Note that checking if it's a dict object is a bad idea, as it rules out dict-like objects. Instead, do try: ... except TypeError: .... (Ask for forgiveness, not permission). - Gareth Latty
Also note that since dicts are by nature unordered, if you have multiple keys "A" in your nested structure, you can never know which one you'll get (like a box of chocolates I suppose ...) - mgilson
@mgilson In this specific, case that's okay and I considered that. :) - Fredrick Brennan
@frb -- I figured that it probably was alright, I just wanted to make sure that it was documented somewhere :). - mgilson

6 Answers

63
votes

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.

31
votes

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
6
votes

Here is a way to do this using a "stack" and the "stack of iterators" pattern (credits to Gareth Rees):

def search(d, key, default=None):
    """Return a value corresponding to the specified key in the (possibly
    nested) dictionary d. If there is no item with that key, return
    default.
    """
    stack = [iter(d.items())]
    while stack:
        for k, v in stack[-1]:
            if isinstance(v, dict):
                stack.append(iter(v.items()))
                break
            elif k == key:
                return v
        else:
            stack.pop()
    return default

The print(search({"B": {"A": 2}}, "A")) would print 2.

1
votes

Just trying to make it shorter:

def get_recursively(search_dict, field):
    if isinstance(search_dict, dict):
        if field in search_dict:
            return search_dict[field]
        for key in search_dict:
            item = get_recursively(search_dict[key], field)
            if item is not None:
                return item
    elif isinstance(search_dict, list):
        for element in search_dict:
            item = get_recursively(element, field)
            if item is not None:
                return item
    return None
0
votes

I couldn't add a comment to the accepted solution proposed by @mgilston because of lack of reputation. The solution doesn't work if the key being searched for is inside a list.

Looping through the elements of the lists and calling the recursive function should extend the functionality to find elements inside nested lists:

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
        elif isinstance(v,list):
            for list_item in v:
                item = _finditem(list_item, key)
                if item is not None:
                    return item

print(_finditem({"C": {"B": [{"A":2}]}}, "A"))
0
votes

I had to create a general-case version that finds a uniquely-specified key (a minimal dictionary that specifies the path to the desired value) in a dictionary that contains multiple nested dictionaries and lists.

For the example below, a target dictionary is created to search, and the key is created with the wildcard "???". When run, it returns the value "D"

def lfind(query_list:List, target_list:List, targ_str:str = "???"):
    for tval in target_list:
        #print("lfind: tval = {}, query_list[0] = {}".format(tval, query_list[0]))
        if isinstance(tval, dict):
            val = dfind(query_list[0], tval, targ_str)
            if val:
                return val
        elif tval == query_list[0]:
            return tval

def dfind(query_dict:Dict, target_dict:Dict, targ_str:str = "???"):
    for key, qval in query_dict.items():
        tval = target_dict[key]
        #print("dfind: key = {}, qval = {}, tval = {}".format(key, qval, tval))
        if isinstance(qval, dict):
            val =  dfind(qval, tval, targ_str)
            if val:
                return val
        elif isinstance(qval, list):
            return lfind(qval, tval, targ_str)
        else:
            if qval == targ_str:
                return tval
            if qval != tval:
                break

def find(target_dict:Dict, query_dict:Dict):
    result = dfind(query_dict, target_dict)
    return result



target_dict = {"A":[
    {"key1":"A", "key2":{"key3": "B"}},
    {"key1":"C", "key2":{"key3": "D"}}]
}
query_dict = {"A":[{"key1":"C", "key2":{"key3": "???"}}]}

result = find(target_dict, query_dict)
print("result = {}".format(result))