Python - Generate a dictionary(tree) from a list of tuples

Here is a simpler approach. (Edited as I realized from Thomas answer that the nodes can be given in any order): Pass 1 creates the nodes (that is, adds them to the nodes dictionary), while Pass 2 then creates the parent<->children structure.

The following assumptions are made: No cycles (it is not clear what the expected output would be in such a case, pointed out by Garret R), no missing edges, no missing tree roots.

a = [(1, 1), (2, 1), (3, 1), (4, 3), (5, 3), (6, 3), (7, 7), (8, 7), (9, 7)]

# pass 1: create nodes dictionary
nodes = {}
for i in a:
    id, parent_id = i
    nodes[id] = { 'id': id }

# pass 2: create trees and parent-child relations
forest = []
for i in a:
    id, parent_id = i
    node = nodes[id]

    # either make the node a new tree or link it to its parent
    if id == parent_id:
        # start a new tree in the forest
        forest.append(node)
    else:
        # add new_node as child to parent
        parent = nodes[parent_id]
        if not 'children' in parent:
            # ensure parent has a 'children' field
            parent['children'] = []
        children = parent['children']
        children.append(node)

print forest

EDIT: Why does your solution not work as you expected?

Here's a hint regarding the top-level: The output you want to obtain is a list of trees. The variable you are dealing with (d), however, needs to be a dictionary, because in function set_nested you apply the setdefaults method to it.

To make this easier, let's define a simple relational object:

class Node(dict):

    def __init__(self, uid):
        self._parent = None  # pointer to parent Node
        self['id'] = uid  # keep reference to id #            
        self['children'] = [] # collection of pointers to child Nodes

    @property
    def parent(self):
        return self._parent  # simply return the object at the _parent pointer

    @parent.setter
    def parent(self, node):
        self._parent = node
        # add this node to parent's list of children
        node['children'].append(self)  

Next define how to relate a collection of Nodes with each other. We will use a dict to hold pointers to each individual Node:

def build(idPairs):
    lookup = {}
    for uid, pUID in idPairs:
        # check if was node already added, else add now:
        this = lookup.get(uid)
        if this is None:
            this = Node(uid)  # create new Node
            lookup[uid] = this  # add this to the lookup, using id as key

        if uid != pUID:
            # set this.parent pointer to where the parent is
            parent = lookup[pUID]
            if not parent:
                # create parent, if missing
                parent = Node(pUID)  
                lookup[pUID] = parent
            this.parent = parent

    return lookup

Now, take your input data and relate it:

a = [(1, 1), (2, 1), (3, 1), (4, 3), (5, 3), (6, 3), (7, 7), (8, 7), (9, 7)]
lookup = build(a)  # can look at any node from here.

for uid in [1, 3, 4]:
    parent = lookup[uid].parent
    if parent:
        parent = parent['id']
    print "%s's parent is: %s" % (uid, parent)

Finally, getting the output: there's a good chance you want to have the data rooted as a a list of unique trees, rather than as a dictionary -- but you can choose what you like.

roots = [x for x in lookup.values() if x.parent is None]

# and for nice visualization:
import json
print json.dumps(roots, indent=4)

yielding:

[
    {
        "id": 1, 
        "children": [
            {
                "id": 2, 
                "children": []
            }, 
            {
                "id": 3, 
                "children": [
                    {
                        "id": 4, 
                        "children": []
                    }, 
                    {
                        "id": 5, 
                        "children": []
                    }, 
                    {
                        "id": 6, 
                        "children": []
                    }
                ]
            }
        ]
    }, 
    {
        "id": 7, 
        "children": [
            {
                "id": 8, 
                "children": []
            }, 
            {
                "id": 9, 
                "children": []
            }
        ]
    } ]