title: Python: Search for and delete nested lists of dictionaries
body: <p>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).</p>
  
  <p>I am still a beginner Pythonist so please forgive the brute-forceness.</p>
  
  <p>Here's a sample dictionary formatted for easy copy and paste.</p>
  
  <pre><code>{'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'}
  </code></pre>
  
  <p>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.</p>
  
  <p>I have tried many different recursive methods but can't seem to get it to work properly.  Any help would be greatly appreciated.</p>
  
  <pre><code>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)
  </code></pre>