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.

---

_{If you are looking for a general explanation of what is wrong with code like this, the canonical is Why does my recursive function return None?. The answers here are mostly specific to the task of searching in a nested dictionary.}

Cosenza

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). – Deutzia

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 ...) – Bethsaida

@Bethsaida In this specific, case that's okay and I considered that. :) – Cosenza

@frb -- I figured that it probably was alright, I just wanted to make sure that it was documented somewhere :). – Bethsaida

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.

Bethsaida

This seems to be the most common mistake when writing recursive functions. – Moisten

@DanielRoseman -- shrugs -- I've made this mistake myself a few times. But it is a hint when your function returns None and you have no idea why ;-) – Bethsaida

Thank you, that should have been obvious. I was looking at this for a good hour! – Cosenza

@frb -- No problem. Stuff like this happens to everyone. – Bethsaida

@Bethsaida Actually, I just realized that this doesn't work when the needed key is second in the dictionary. Any clues about that? It's because it's returning after the first key, value in obj.items(). – Cosenza

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.items():

        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

Redmund

replace iteritems() with items() to get this working in python3: docs.buildbot.net/0.9.4/developer/py3-compat.html – Willardwillcox

with isinstance(value, (list, tuple)) it will search in nested tuples as well – Berceuse

This only searches dictionary keys - it does not match values. That's expected! And it's what the OP is asking for. And it's a good answer. Just wanted to warn those who may have glossed over that ... like me. :P – Eb

Answer 3

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.

Tram

Answer 4

Here's a Python 3.3+ solution which can handle lists of lists of dicts. It also uses duck typing, so it can handle any iterable, or object implementing the 'items' method.

from typing import Iterator
def deep_key_search(obj, key: str) -> Iterator:
    """ Do a deep search of {obj} and return the values of all {key} attributes found.
    :param obj: Either a dict type object or an iterator.
    :return: Iterator of all {key} values found"""

    if isinstance(obj, str):
        # When duck-typing iterators recursively, we must exclude strings
        return

    try:
        # Assume obj is a like a dict and look for the key
        for k, v in obj.items():
            if k == key:
                yield v
            else:
                yield from deep_key_search(v, key)
    except AttributeError:
        # Not a dict type object. Is it iterable like a list?
        try:
            for v in obj:
                yield from deep_key_search(v, key)
        except TypeError:
            pass  # Not iterable either.

Pytest:

@pytest.mark.parametrize(
    "data, expected, dscr", [
        ({}, [], "Empty dict"),
        ({'Foo': 1, 'Bar': 2}, [1], "Plain dict"),
        ([{}, {'Foo': 1, 'Bar': 2}], [1], "List[dict]"),
        ([[[{'Baz': 3, 'Foo': 'a'}]], {'Foo': 1, 'Bar': 2}], ['a', 1], "Deep list"),
        ({'Foo': 1, 'Bar': {'Foo': 'c'}}, [1, 'c'], "Dict of Dict"),
        (
            {'Foo': 1, 'Bar': {'Foo': 'c', 'Bar': 'abcdef'}},
            [1, 'c'], "Contains a non-selected string value"
        ),
    ])
def test_deep_key_search(data, expected, dscr):
    assert list(deep_key_search(data, 'Foo')) == expected

Cleaning

Answer 5

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

Sideslip

Answer 6

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"))

Liam

Answer 7

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))

Hereinto

Answer 8

Thought I'd throw my hat in the ring, this will allow for recursive requests on anything that implements a __getitem__ method.

def _get_recursive(obj, args, default=None):
    """Apply successive requests to an obj that implements __getitem__ and
    return result if something is found, else return default"""
    if not args:
        return obj
    try:
        key, *args = args
        _obj = object.__getitem__(obj, key)
        return _get_recursive(_obj, args, default=default)
    except (KeyError, IndexError, AttributeError):
        return default

Kreager

Answer 9

def recursive_search(json_data, target_key, result=None):
    if result is None:
        result = []

    if isinstance(json_data, dict):
        for key, value in json_data.items():
            if key == target_key:
                result.append(value)
            else:
                recursive_search(value, target_key, result)
    elif isinstance(json_data, list):
        for item in json_data:
            recursive_search(item, target_key, result)

    return result

For me this works like charm

Conflux

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Kindred