12

From the following nested dictionary, how can I get every parent dictionary key of 'value4ac'? By starting the 'value4ac' value, I want to get 'key4', 'key4a', 'Key4ac'.

example_dict = { 'key1' : 'value1',
                 'key2' : 'value2',
                 'key3' : { 'key3a': 'value3a' },
                 'key4' : { 'key4a': { 
                                         'key4aa': 'value4aa',
                                         'key4ab': 'value4ab',
                                         'key4ac': 'value4ac'
                                     },
                            'key4b': 'value4b'
                           }
                   }
Carlos
  • 2,222
  • 12
  • 21
Jym Morrison
  • 185
  • 1
  • 3
  • 9
  • Is there a logic behind the key name? I mean, do you know that `'key4ac'` will be in the `dict` "referenced" by `key4`? – Bakuriu Mar 04 '13 at 20:08

4 Answers4

20

recursion to the rescue!

example_dict = { 'key1' : 'value1',
                 'key2' : 'value2',
                 'key3' : { 'key3a': 'value3a' },
                 'key4' : { 'key4a': { 'key4aa': 'value4aa',
                                       'key4ab': 'value4ab',
                                       'key4ac': 'value4ac'},
                            'key4b': 'value4b'}
                }

def find_key(d, value):
    for k,v in d.items():
        if isinstance(v, dict):
            p = find_key(v, value)
            if p:
                return [k] + p
        elif v == value:
            return [k]

print find_key(example_dict,'value4ac')

how it works

It looks through the items and checks 2 cases

  • item isn't a dictionary -- In this case, see if it is the value we're looking for. If it is, return a list which contains only the key. (This is our base-case for recursion).
  • item is a dictionary -- Try looking for the key in that dictionary. If it is found in that dictionary (or any sub-dict), return the key which takes the right path pre-pended onto the rest of the path.
mgilson
  • 300,191
  • 65
  • 633
  • 696
  • by `def find_key(d,key):` you mean `def find_key(d,value):`, correct? – zelusp Jul 12 '16 at 20:39
  • @zelusp -- Yes, the name of that variable was ... Unfortunate. :-). Thanks for the suggestion. – mgilson Jul 12 '16 at 20:41
  • How to find multiple occurences? For example a list of lists with the key paths. E.g.: `[['key4', 'key4a', 'key4ac'], ['key5, 'key5a', 'key5ac']]` – Blind0ne Apr 19 '21 at 09:41
9

What if your dictionary contains lists too?

Here's a more broad variant of @mgilson 's solution, suitable for JSON:

example_dict_with_list = { 'key1' : 'value1',
                           'key2' : 'value2',
                           'key3' : { 'key3a': 'value3a' },
                           'key4' : { 'key4a': [{ 'key4aa': 'value4aa',
                                                  'key4ab': 'value4ab',
                                                  'key4ac': 'value4ac'}],
                                      'key4b': 'value4b'}
                          }

def breadcrumb(json_dict_or_list, value):
  if json_dict_or_list == value:
    return [json_dict_or_list]
  elif isinstance(json_dict_or_list, dict):
    for k, v in json_dict_or_list.items():
      p = breadcrumb(v, value)
      if p:
        return [k] + p
  elif isinstance(json_dict_or_list, list):
    lst = json_dict_or_list
    for i in range(len(lst)):
      p = breadcrumb(lst[i], value)
      if p:
        return [str(i)] + p

print(
    breadcrumb(example_dict_with_list, 'value4aa')
)

Which returns

['key4', 'key4a', '0', 'key4aa', 'value4aa']

Bonus

If you need to print it out nicely, like a string of breadcrums, do

print(
  ' > '.join(
    breadcrumb(example_dict, 'value4aa')
  )
)

Which will return

'key4 > key4a > 0 > key4aa > value4aa'
KiriSakow
  • 957
  • 1
  • 12
  • 22
  • A perfect answer! For me, it should be more clear `def breadcrumb(json_dict_or_list, value) -> list:` and `p: list = breadcrumb(v, value)` – lam vu Nguyen Jun 01 '23 at 10:07
0

You can use a NestedDict.

>>> from ndicts.ndicts import NestedDict
>>> example_dict = { 'key1' : 'value1',
...                  'key2' : 'value2',
...                  'key3' : { 'key3a': 'value3a' },
...                  'key4' : { 'key4a': {
...                                          'key4aa': 'value4aa',
...                                          'key4ab': 'value4ab',
...                                          'key4ac': 'value4ac'
...                                      },
...                             'key4b': 'value4b'
...                            }
...                    }
>>> nd = NestedDict(example_dict)
>>> for key, value in nd.items():
...     if value == "value4ac":
...             print(key)
...
('key4', 'key4a', 'key4ac')

To install ndicts

pip install ndicts
edd313
  • 1,109
  • 7
  • 20
0

Solution that supports dicts keys and lists elements

Slight modification of @KiriSakow solution (whom was inspired by @mgilson).

It will not produce a list index and returns correct parents not only for the last child, but for sub-parents as well.

def breadcrumb(nested_dict, value):
    if nested_dict == value:
        return [nested_dict]
    elif isinstance(nested_dict, dict):
        for k, v in nested_dict.items():
            if k == value:
                return [k]
            p = breadcrumb(v, value)
            if p:
                return [k] + p
    elif isinstance(nested_dict, list):
        lst = nested_dict
        for i in range(len(lst)):
            p = breadcrumb(lst[i], value)
            if p:
                return p

Input

example_dict_with_list = { 'key1' : 'value1',
                           'key2' : 'value2',
                           'key3' : { 'key3a': 'value3a' },
                           'key4' : { 'key4a': [{ 'key4aa': 'value4aa',
                                                  'key4ab': 'value4ab',
                                                  'key4ac': 'value4ac'}],
                                      'key4b': 'value4b'}
                          }


print(breadcrumb(example_dict_with_list, "value4aa"))
print(breadcrumb(example_dict_with_list, "key4aa"))

Output

['key4', 'key4a', 'key4aa', 'value4aa']
['key4', 'key4a', 'key4aa']
Alex Kopylov
  • 1
  • 3