Build nested tree-like dict from an array of dicts with children

Question

I have an array of dicts retrieved from a web API. Each dict has a name, description, 'parent', and children key. The children key has an array of dicts as it value. For the sake of clarity, here is a dummy example:

[
  {'name': 'top_parent', 'description': None, 'parent': None,
   'children': [{'name': 'child_one'},
                {'name': 'child_two'}]},
  {'name': 'child_one', 'description': None, 'parent': 'top_parent',
   'children': []},
  {'name': 'child_two', 'description': None, 'parent': 'top_parent',
   'children': [{'name': 'grand_child'}]},
  {'name': 'grand_child', 'description': None, 'parent': 'child_two',
   'children': []}
]

Every item in in the array. An item could be the top-most parent, and thus not exist in any of the children arrays. An item could be both a child and a parent. Or an item could only be a child (have no children of its own).

So, in a tree structure, you'd have something like this:

top_parent
  child_one
  child_two
    grand_child

In this contrived and simplified example top_parent is a parent but not a child; child_one is a child but not a parent; child_two is a parent and a child; and grand_child is a child but not a parent. This covers every possible state.

What I want is to be able to iterate over the array of dicts 1 time and generate a nested dict that properly represents the tree structure (however, it 1 time is impossible, the most efficient way possible). So, in this example, I would get a dict that looked like this:

{
  'top_parent': {
    'child_one': {},
    'child_two': {
      'grand_child': {}
    }
  }    
}

Strictly speaking, it is not necessary to have item's without children to not be keys, but that is preferable.

Answer 1

Fourth edit, showing three versions, cleaned up a bit. First version works top-down and returns None, as you requested, but essentially loops through the top level array 3 times. The next version only loops through it once, but returns empty dicts instead of None.

The final version works bottom up and is very clean. It can return empty dicts with a single loop, or None with additional looping:

from collections import defaultdict

my_array = [
  {'name': 'top_parent', 'description': None, 'parent': None,
   'children': [{'name': 'child_one'},
                {'name': 'child_two'}]},
  {'name': 'child_one', 'description': None, 'parent': 'top_parent',
   'children': []},
  {'name': 'child_two', 'description': None, 'parent': 'top_parent',
   'children': [{'name': 'grand_child'}]},
  {'name': 'grand_child', 'description': None, 'parent': 'child_two',
   'children': []}
]

def build_nest_None(my_array):
    childmap = [(d['name'], set(x['name'] for x in d['children']) or None)
                for d in my_array]
    all_dicts = dict((name, kids and {}) for (name, kids) in childmap)
    results = all_dicts.copy()
    for (name, kids) in ((x, y) for x, y in childmap if y is not None):
        all_dicts[name].update((kid, results.pop(kid)) for kid in kids)
    return results

def build_nest_empty(my_array):
    all_children = set()
    all_dicts = defaultdict(dict)
    for d in my_array:
        children = set(x['name'] for x in d['children'])
        all_dicts[d['name']].update((x, all_dicts[x]) for x in children)
        all_children.update(children)
    top_name, = set(all_dicts) - all_children
    return {top_name: all_dicts[top_name]}


def build_bottom_up(my_array, use_None=False):
    all_dicts = defaultdict(dict)
    for d in my_array:
        name = d['name']
        all_dicts[d['parent']][name] = all_dicts[name]

    if use_None:
        for d in all_dicts.values():
            for x, y in d.items():
                if not y:
                    d[x] = None

    return all_dicts[None]

print(build_nest_None(my_array))
print(build_nest_empty(my_array))
print(build_bottom_up(my_array, True))
print(build_bottom_up(my_array))

Results in:

{'top_parent': {'child_one': None, 'child_two': {'grand_child': None}}}
{'top_parent': {'child_one': {}, 'child_two': {'grand_child': {}}}}
{'top_parent': {'child_one': None, 'child_two': {'grand_child': None}}}
{'top_parent': {'child_one': {}, 'child_two': {'grand_child': {}}}}

Answer 2

You can keep a lazy mapping from names to nodes and then rebuild the hierarchy by processing just the parent link (I'm assuming data is correct, so if A is marked as the parent of B iff B is listed among the children of A).

nmap = {}
for n in nodes:
    name = n["name"]
    parent = n["parent"]
    try:
        # Was this node built before?
        me = nmap[name]
    except KeyError:
        # No... create it now
        if n["children"]:
            nmap[name] = me = {}
        else:
            me = None
    if parent:
        try:
            nmap[parent][name] = me
        except KeyError:
            # My parent will follow later
            nmap[parent] = {name: me}
    else:
        root = me

The children property of the input is used only to know if the element should be stored as a None in its parent (because has no children) or if it should be a dictionary because it will have children at the end of the rebuild process. Storing nodes without children as empty dictionaries would simplify the code a bit by avoiding the need of this special case.

Using collections.defaultdict the code can also be simplified for the creation of new nodes

import collections
nmap = collections.defaultdict(dict)
for n in nodes:
    name = n["name"]
    parent = n["parent"]
    me = nmap[name]
    if parent:
        nmap[parent][name] = me
    else:
        root = me

This algorithm is O(N) assuming constant-time dictionary access and makes only one pass on the input and requires O(N) space for the name->node map (the space requirement is O(Nc) for the original nochildren->None version where Nc is the number of nodes with children).