Find key recursively in dictionary and then list all parent keys

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

>Solution :

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.