How to find all occurrence of a key in nested dict, but also keep track of the outer dict key value?

Question

I've searched over stackoverflow and found the following code that allow me to search for a key values in nested dict recursively. However, I also want to keep track of the outer dict's key value. How should I do that?

from Alfe's answer in the below link, I can use the code below get all the values of the key in nested dict. Find all occurrences of a key in nested python dictionaries and lists

data = {'item1': {
  'name': 'dummy',
  'type': 'dummy1'},

'item2': {
  'name': 'dummy',
  'type': 'dummy1',
  'label':'label2'
},

'item3': {
  'name': 'dummy',
  'type': 'dummy1',
  'label':'label3'},

'item4': {
  'name': 'dummy',
  'type': 'dummy1'}
}

 def find(key, dictionary):
    for k, v in dictionary.items():
        if k == key:
            yield v
        elif isinstance(v, dict):
            for result in find(key, v):
                yield result
        elif isinstance(v, list):
            for d in v:
                for result in find(key, d):
                    yield result


In[1]:list(find('label', data))
Out[1]: 
['label2', 'label3']

However, I also need to keep record of the outer dict key as below. How should I do this? Also my data can potentially have more than one layer.

{'item2':'label2',
'item3':'label3'
}

I also find the recursive_lookup in this link very neatly written. However, it's returning None when I tried to run it.

Find keys in nested dictionary

def recursive_lookup(k, d):
    if k in d:
        return d[k]
    for v in d.values():
        if isinstance(v, dict):
            return recursive_lookup(k, v)
    return None

It's returning None when I call recursive_lookup('label', data).

If anyone can point out for me why the above code is not working that would be great too!

Answer 1

This should work regardless of how deep your nesting is (up to the stack limit, at any rate). The request for keeping track of the dict's key is a little awkward--I used a tuple to return the pair. Note that if the found value is in the outermost dictionary, it won't be in the tuple format.

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

    for k, v in d.items():
        if isinstance(v, dict):
            result = recursive_lookup(key, v)

            if result:
                return k, result


print(recursive_lookup('label', data))

Output:

('item2', 'label2')

Here's a version that's a little messier (I'm not crazy about an inner function, but at least the accumulator list isn't a parameter and isn't global) but will return a list of all found items nested up to the stack limit, excepting the outermost keys:

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

        for k, v in d.items():
            if isinstance(v, dict):
                result = _lookup(key, v)

                if result:
                    accumulator.append((k, result))

    accumulator = []
    _lookup(key, d)
    return accumulator

Output:

[('item3', 'label3'), ('item2', 'label2')]

This can be easily modified if you want to output a dict--replace accumulator = [] with accumulator = {} and accumulator.append((k, result)) with accumulator[k] = result, but this might be awkward to work with, and you can't store duplicate key entries.

As for your final question, the reason you're getting None is because the inner loop returns after checking the first item whether it found something or not. Since label is in the second location of the items() array, it never gets looked at.