Recursively Iterate Through A Nested Dict And Return Value Of The First Matching Key

I have a deeply nested dict and need to iterate through it and return the value corresponding to the key argument, second argument of my function. For example, with tree = {'a': 12

Solution 1:

You have to check whether the recursive call actually found something so you can continue the loop. E.g. try the following:

deftree_traverse(tree, key):
    if key in tree:
        return tree[key]
    for v infilter(dict.__instancecheck__, tree.values()):
        if (found := tree_traverse(v, key)) isnotNone:  
            return found
 

Solution 2:

Here we instantiate an object when the function is created, that all executions of the function will share, called _marker. We return this object if we don't find the key. (You could also use None here, but None is frequently a meaningful value.)

deftree_traverse(tree, key, *, _marker=object()):
    for k,v  in tree.items():
        ifisinstance(v, dict):
            res = tree_traverse(v, key, _marker=_marker)
            if res isnot _marker:
                return res
        elif k == key:
            return v
    return _marker

deffind(tree, key):
    _marker = object()
    res = tree_traverse(tree, key, _marker=_marker)
    if res is _marker:
        raise KeyError("Key {} not found".format(key))
    return res

I use tree_traverse as a helper function because we want different behaviour at the outermost layer of our recursion (throw an error) than we want inside (return a _marker object)