Python recursive function to match key values and return path in nested dictionary

Question

I have a nested dictionary, and I am trying to write a function that will find matching keys, and return all the keys in the path to the key that matches. Given the example nested dictionary below:

nested_dict = {'a': {'b':{'c': 'd',
                      'e': 'f'},
                 'g': {'h': {'i': 'j'}}},
           'k': {'l': 'm',
                 'n': 'o',
                 'p': {'q': 'r',
                       's': 't'}}}

I want the function getpath to return:

getpath(s) = ['k','p','s']
getpath(i) = ['a', 'g','h','i']

I wrote the recursive function below to try to accomplish this, but it's not returning anything, I'm hoping I'm close but am making a small error:

start_keys = list()
def getpath(nested_dict,search_value,keys):
    # extract keys from the dict
    dict_keys = list(nested_dict.keys())
    # loop through dict keys
    for key in dict_keys:
        # append key to keys
        keys.append(key)
        level_down = nested_dict[key]
        # check if the key matches the target value
        if search_value.lower()==key.lower():
            # if it does match, we're good, so return keys
            return(keys)
        else:
            # since it didn't match, we attempt to go further down
            if type(level_down) is dict:
                # run getpath on it
                getpath(level_down, search_value, keys)
            else:
                # if we can't go further down, it means we got to the end without finding a match, so we wipe out keys
                keys = list()

Nick · Accepted Answer · 2021-02-13 02:13:29Z

4

You can simplify your recursion by just checking whether the current key matches the search_value or if not, if the associated value is a dict, in which case you recurse:

def getpath(nested_dict, search_value):
    # loop through dict keys
    for key in nested_dict.keys():
        # have we found the search value?
        if key == search_value:
            return [key]
        # if not, search deeper if this value is a dict
        if type(nested_dict[key]) is dict:
            path = getpath(nested_dict[key], search_value)
            if path is not None:
                return [key] + path
    # no match found in this part of the dict
    return None


getpath(nested_dict,'s')     # ['k','p','s']
getpath(nested_dict, 'i')    # ['a', 'g','h','i']

answered Feb 13, 2021 at 2:13

Nick

147k23 gold badges67 silver badges106 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Ajax1234 · Accepted Answer · 2021-02-13 02:09:08Z

1

You can use recursion with a generator:

def getpath(k, d, c = []):
   for a, b in getattr(d, 'items', lambda :[])():
      if a == k:
         yield from (c+[a])
      else:
          yield from getpath(k, d = b, c = c+[a])
   

nested_dict = {'a': {'b': {'c': 'd', 'e': 'f'}, 'g': {'h': {'i': 'j'}}}, 'k': {'l': 'm', 'n': 'o', 'p': {'q': 'r', 's': 't'}}}
print(list(getpath('s', d=nested_dict)))
print(list(getpath('i', d=nested_dict)))

Output:

['k', 'p', 's']
['a', 'g', 'h', 'i']

answered Feb 13, 2021 at 2:09

Ajax1234

71.7k9 gold badges67 silver badges110 bronze badges

Collectives™ on Stack Overflow

Python recursive function to match key values and return path in nested dictionary

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related