Python: How can I filter a n-nested dict of dicts by leaf value?

Question

I've got a dict that looks something like this:

d = {'Food': {'Fruit'  : {'Apples'    : {'Golden Del.'  : ['Yellow'],
                                         'Granny Smith' : ['Green'],
                                         'Fuji'         : ['Red'],    
                                        },
                          'Cherries'  : ['Red'],
                          'Bananas'   : ['Yellow'],
                          'Grapes'    : {'Red Grapes'   : ['Red'],
                                         'Green Grapes' : ['Green'],  
                                        },
                          },
              'Dessert': {'Baked Ds' : {'Cakes'         : {'Yellow Cake' : ['Yellow'],
                                                           'Red Velvet'  : ['Red'],
                                                          },
                                         'Cookies'      : ['Yellow'],
                                        },
                          },
              'Steak'  : ['Red'],
             },
     'Other': ['Blue'],
    }

So basically, an n-nested dict, where each value is either another dict or a list containing a single item.

Let's say that I want to filter this by a single list item, say, 'Red' such that the result would be:

d = {'Food': {'Fruit'  : {'Apples'    : {'Fuji'        : ['Red'],    
                                        },
                          'Cherries'  : ['Red'],
                          'Grapes'    : {'Red Grapes'  : ['Red'], 
                                        },
                          },
              'Dessert': {'Baked Ds' : {'Cakes'        : {'Red Velvet'  : ['Red'],
                                                          },
                                        },
                          },
              'Steak'  : ['Red'],
             },
    }

So that the structure remains the same but everything that doesn't have 'Red' as its list item is removed, all the way up the hierarchy.

Any suggestions? I've messed around with this for a while and came up with this, but it doesn't seem to work:

def filterNestedDict(node, searchItem):
    if isinstance(node,list):
        return node
    else:
        for key, value in node.iteritems():
            if isinstance(value,dict) and value is not {}:
                return {key: filterNestedDict(value,searchItem)}
            elif searchItem in value:
                return {key: filterNestedDict(value,searchItem)}

return filterNestedDict(bigTree, searchItem)

I suspect it's just an issue of recursion, but any suggestions would be greatly appreciated.

Thanks!

Answer 1

You were pretty close, this should do the trick for you:

def filter_nested_dict(node, search_term):
    if isinstance(node, list):
        if node[0] == search_term:
            return node
        else:
            return None
    else:
        dupe_node = {}
        for key, val in node.iteritems():
            cur_node = filter_nested_dict(val, search_term)
            if cur_node:
                dupe_node[key] = cur_node
        return dupe_node or None