Find key recursively in dictionary and then list all parent keys

Question

My question is similar to Finding a key recursively in a dictionary except that once I find the key, I would like to list all parent keys that lead me to the target key.

Logically, I feel like I know what I need to do: store the "path" by appending keys to a list as I descend into the dictionary. If I get to the "bottom" of the dictionary and don't find the key I'm looking for, then I need to reset the path. But, I can't think how do implement this in Python. My current solution just prints out the target key in a list:

def list_parents(obj, key):
    path = []
    if key in obj: 
        path.append(key)
        return path

    for k, v in obj.items():
        if isinstance(v, dict):
            path.extend(list_parents(v, key))

    return path

Dani Mesejo · Accepted Answer · 2022-07-29T22:36:54.837

Try adding the path as an optional parameter:

def list_parents(obj, key, path=[]):
    if key in obj:
        path.append(key)
        return path

    for k, v in obj.items():
        if isinstance(v, dict):
            found = list_parents(v, key, path=path + [k])
            if found:
                return found

    return None


keys = ["A", "E", "G"]
for key in keys:
    res = list_parents({"B": {"A": 2}, "C": 1, "D": {"E": 3, "F": {"G": 3}}, }, key)
    print(res)

Output

['B', 'A']
['D', 'E']
['D', 'F', 'G']

Or as an alternative:

def list_parents(obj, key):
    if key in obj:
        return [key]

    for k, v in obj.items():
        if isinstance(v, dict):
            found = list_parents(v, key)
            if found:
                return [k, *found]

    return None

To improve the complexity of the above approach you could use a deque:

from collections import deque


def list_parents(obj, key):
    if key in obj:
        return deque([key])

    for k, v in obj.items():
        if isinstance(v, dict):
            found = list_parents(v, key)
            if found:
                found.appendleft(k)
                return found
    return None

The reason to use a deque is that inserting to the front of a list (the line [k, *found]) is O(n) vs O(1) in a deque.

Why does `path` need to be an optional parameter? Because otherwise you overwrite it with an empty list on each recursion? — Sterling Butters, Jul 29 '22 at 22:32
That is a trick to keep the state between functions calls, is actually not a best practice. I suggest you use the second alternative — Dani Mesejo, Jul 29 '22 at 22:34

score 1 · Answer 2 · answered Jul 29 '22 at 22:42

Alternatively, you could try this way. It still uses recursion to search through the nested dict.

dc  = { 'A' : 'vaa',
        'B' : 'vbb',
        'C' : { 'kc': 'vcc' },
        'D' : { 'kd': { 'kdd1': 'dd1',
                        'kdd11': 'abcc',
                        'key12': 'abcd'},
                    'kdd2': 'dd2'}
                }

def find_parents(D, value):
    for k, v in D.items():
        if isinstance(v, dict):
            parent = find_parents(v, value)  # <--- search down
            if parent:
                return [k] + parent
        elif v == value:
            return [k]

print(find_parents(dc,'abcd')      # ['D', 'kd', 'key12']

score 0 · Answer 3 · answered Jul 29 '22 at 22:31

Another solution:

You can make recursive generator that yields all paths. In your program you will do a check if the path is "correct" (e.g. the last element in path is your key):

dct = {"a": {"b": {}, "c": {"d": "xxx"}}}


def list_parents(obj, path=None):
    if path is None:
        path = []

    if isinstance(obj, dict):
        for k, v in obj.items():
            yield (p := path + [k])
            yield from list_parents(v, p)


key = "d"
path = next(path for path in list_parents(dct) if path[-1] == key)
print(".".join(path))

Prints:

a.c.d

Find key recursively in dictionary and then list all parent keys

3 Answers3