Python: Search for and delete nested lists of dictionaries
Question: I have a tree of nested lists and dictionaries that I need to recursively go
through and remove entire dictionaries that match specific criteria. For
instance, I need to remove all dictionaries with the 'type' of 'Folder' that
have no children (or an empty list of children).

I am still a beginner Pythonist so please forgive the brute-forceness.

Here's a sample dictionary formatted for easy copy and paste.

    
    
    {'children': [{'children': [{'key': 'group-1',
                             'name': 'PRD',
                             'parent': 'dc-1',
                             'type': 'Folder'},
                            {'children': [{'key': 'group-11',
                                           'name': 'App1',
                                           'parent': 'group-2',
                                           'type': 'Folder'}],
                             'key': 'group-2',
                             'name': 'QA',
                             'parent': 'dc-1',
                             'type': 'Folder'},
                            {'key': 'group-3',
                             'name': 'Keep',
                             'parent': 'dc-1',
                             'type': 'Host'}],
               'key': 'dc-1',
               'name': 'ABC',
               'parent': 'root',
               'type': 'Datacenter'}],
    'key': 'root',
    'name': 'Datacenters',
    'parent': None,
    'type': 'Folder'}
    

In this dictionary the only tree that should remain is /root/dc-1/group-3. The
group-11 folder should be deleted first, then its parent (since the child is
no longer there), etc.

I have tried many different recursive methods but can't seem to get it to work
properly. Any help would be greatly appreciated.

    
    
    def cleanup(tree):
        def inner(tree):
            if isinstance(tree, dict):
                if 'type' in tree and tree['type'] == 'Folder':
                    if 'children' not in tree or not tree['children']:
                        print 'Deleting tree: ' + str(tree['name'])
                        if str(tree['key']) not in del_nodes:
                            del_nodes.append(str(tree['key']))
                    else:
                        for item in tree.values():
                            inner(item)
                            # Delete empty folders here
                            if del_nodes:
                                print 'Perform delete here'
                                if 'children' in tree and isinstance(tree['children'], (list, tuple)):
                                    getvals = operator.itemgetter('key')
                                    tree['children'].sort(key=getvals)
                                    result = []
                                    # groupby is the wrong method.  I need a list of tree['children'] that doesn't contain keys in del_nodes
                                    for k, g in itertools.groupby(tree['children'], getvals):
                                        result.append(g.next())
    
                                        tree['children'][:] = result
    
                                del_nodes = []
                else:
                    for item in tree.values():
                        inner(item)
            elif isinstance(tree, (list, tuple)):
                for item in tree:
                    inner(item)
    
                    if isinstance(item, dict):
                        if 'type' in item and item['type'] == 'Folder':
                            if 'children' not in item or not item['children']:
                                print 'Delete ' + str(item['name'])
                                if str(item['key']) not in del_nodes:
                                    del_nodes.append(str(item['key']))
                    elif isinstance(item, (list, tuple)):
                        if not item:
                            print 'Delete ' + str(item['name'])
                            if str(item['key']) not in del_nodes:
                                del_nodes.append(str(item['key']))
    
        inner(tree)
    


Answer: I'd suggest you write a function to walk your datastructure and call a
function on each node.

_Updated to avoid the "deleting item from iterated sequence" bug_

**E.g.**

    
    
    def walk(node,parent=None,func=None):
      for child in list(node.get('children',[])):
        walk(child,parent=node,func=func)
      if func is not None:
        func(node,parent=parent)
    
    def removeEmptyFolders(node,parent):
      if node.get('type') == 'Folder' and len(node.get('children',[])) == 0:
        parent['children'].remove(node)
    
    d = {'children': [{'children': [{'key': 'group-1',
                             'name': 'PRD',
                             'parent': 'dc-1',
                             'type': 'Folder'},
                            {'children': [{'key': 'group-11',
                                           'name': 'App1',
                                           'parent': 'group-2',
                                           'type': 'Folder'}],
                             'key': 'group-2',
                             'name': 'QA',
                             'parent': 'dc-1',
                             'type': 'Folder'},
                            {'key': 'group-3',
                             'name': 'Keep',
                             'parent': 'dc-1',
                             'type': 'Host'}],
               'key': 'dc-1',
               'name': 'ABC',
               'parent': 'root',
               'type': 'Datacenter'}],
    'key': 'root',
    'name': 'Datacenters',
    'parent': None,
    'type': 'Folder'}
    

**Notes**

  * _Walk_ function uses three arguments, the child node, the parent node and the _work_ function.
  * The _walk_ function calls the _work_ function after visiting the child nodes.
  * The _work_ function takes both child and parent nodes as arguments so pruning the child is as easy as `parent['children'].remove(child)`
  * _Update_ : As noticed in the comments, if you delete from a sequence while iterating, it will skip elements. `for child in list(node.get('children',[]))` in the `walk` function copies the list of children allowing the entries to be removed from the parent's key without skipping.

**Then** :

    
    
    >>> walk(d,func=removeEmptyFolders)
    >>> from pprint import pprint
    >>> pprint(d)
    {'children': [{'children': [{'key': 'group-3',
                                 'name': 'Keep',
                                 'parent': 'dc-1',
                                 'type': 'Host'}],
                   'key': 'dc-1',
                   'name': 'ABC',
                   'parent': 'root',
                   'type': 'Datacenter'}],
     'key': 'root',
     'name': 'Datacenters',
     'parent': None,
     'type': 'Folder'}
    

