4

I have a large nested dictionary with an unknown depth and i would like to know how i can find the keys which led to the value. For example...

{'furniture':{'chair':{'sofa':{'cushion':{}}}}}

Ideally what i am looking for is a function to determine the path to the value that i have entered. I have tried researching online and this is what i tried...

def route(d,key):
    if key in d: return d[key]

    for k,v in d.items():
        if isinstance(v,dict):
            item = route(v, key)
            if item is not None:
                return item

This returns the items inside the key. I am looking to be able to extract the path which leads to that item. For example, route(dictionary,'sofa') then i would be able to get an expected output as such or something similar...

{'sofa':{'chair':'furniture'}}

What are some of the ways that i can achieve this ? Thanks for your help

Cua
  • 129
  • 9

1 Answers1

3

You can do this recursively and return a list of keys that lead you to your target key:

def route(d, key):
    if key in d: return [key]
    for k, v in d.items():
        if type(v) == dict:
            found = route(v, key)
            if found: return [k] + found
    return []

If we run this on the following dictionary:

data = {
    'furniture': {
        'chair': {
            'sofa': {
                'cushion': {}
            }
        }
    },
    'electronics': {
        'tv': {
            'samsung43': 800,
            'tcl54': 200
        }
    }
}

print(route(data, 'cushion'))
print(route(data, 'tcl54'))
print(route(data, 'hello'))

we get the following output:

['furniture', 'chair', 'sofa', 'cushion']
['electronics', 'tv', 'tcl54']
[]
slider
  • 12,810
  • 1
  • 26
  • 42
  • hi this is great, but im getting a maximum recursion depth error when i run it to search for something which has multiple values associated to it. example, `{'furniture':{'chair':{'sofa':{'cushion':{},'cushion2':{},'soft cushion':{}}}}}` – Cua Nov 23 '18 at 01:22
  • hi my apologies. it works well for me too.. i guess my dataset is just too big, i cant search for values that are at the bottom of the dataset :( – Cua Nov 23 '18 at 01:28
  • @Cua that is strange, how big is it? – slider Nov 23 '18 at 01:30
  • 175,000 kilobytes – Cua Nov 23 '18 at 01:35
  • @Cua I haven't tried this before but perhaps you can try setting a higher recursion depth limit: https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it – slider Nov 23 '18 at 01:39
  • 1
    Thank you for your help. But unfortunately, i have tried it and my kernel begins to fail/shutdown at around 3000-3500 and its still not sufficient – Cua Nov 23 '18 at 01:45