recursively build hierarchical JSON tree in python
Question: I have a database of parent-child connections. The data look like the
following but could be presented in whichever way you want (dictionaries, list
of lists, JSON, etc).

    
    
    links=(("Tom","Dick"),("Dick","Harry"),("Tom","Larry"),("Bob","Leroy"),("Bob","Earl"))
    

The output that I need is a hierarchical JSON tree, which will be rendered
with d3. There are discrete sub-trees in the data, which I will attach to a
root node. So I need to recursively go though the links, and build up the tree
structure. The furthest I can get is to iterate through all the people and
append their children, but I can't figure out to do the higher order links
(e.g. how to append a person with children to the child of someone else). This
is similar to another question
[here](http://stackoverflow.com/questions/10737273/recursive-function-to-
create-hierarchical-json-object), but I have no way to know the root nodes in
advance, so I can't implement the accepted solution.

I am going for the following tree structure from my example data.

    
    
    {
    "name":"Root",
    "children":[
        {
         "name":"Tom",
         "children":[
             {
             "name":"Dick",
             "children":[
                 {"name":"Harry"}
             ]
             },
             {
              "name":"Larry"}
         ]
        },
        {
        "name":"Bob",
        "children":[
            {
            "name":"Leroy"
            },
            {
            "name":"Earl"
            }
        ]
        }
    ]
    }
    

This structure renders like this in my d3 layout. ![Rendered
image](http://i.stack.imgur.com/1Acgc.png)


Answer: To identify the root notes you can unzip `links` and look for parents who are
not children:

    
    
    parents, children = zip(*links)
    root_nodes = {x for x in parents if x not in children}
    

Then you can apply the recursive method:

    
    
    import json
    
    links = [("Tom","Dick"),("Dick","Harry"),("Tom","Larry"),("Bob","Leroy"),("Bob","Earl")]
    parents, children = zip(*links)
    root_nodes = {x for x in parents if x not in children}
    for node in root_nodes:
        links.append(('Root', node))
    
    def get_nodes(node):
        d = {}
        d['name'] = node
        children = get_children(node)
        if children:
            d['children'] = [get_nodes(child) for child in children]
        return d
    
    def get_children(node):
        return [x[1] for x in links if x[0] == node]
    
    tree = get_nodes('Root')
    print json.dumps(tree, indent=4)
    

I used a set to get the root nodes, but if order is important you can use a
list and [remove the
duplicates](http://stackoverflow.com/questions/10549345/how-to-remove-
duplicate-items-from-a-list-using-list-comprehension).

