tree.py

rs = [
    (1, 0),
    (2, 1),
    (3, 1),
    (4, 2),
    (5, 4),
]

class Node(object):

    def __init__(self, name):
        self.name = name
        self.children = []

    def __eq__(self, other):
        return self.name == other.name

    def add_child(self, node):
        if node not in self.children:
            self.children.append(node)

    @classmethod
    def get_node(cls, store, name):
        if name not in store:
            store[name] = cls(name)
        return store[name]


def make_tree(rs, top):
    store = {}
    chains = {name: parent for name, parent in rs}

    def make_chain(name):
        yield name
        while 1:
            if name in chains:
                name = chains[name]
                yield name
            else:
                break

    for name, _ in rs:
        name_chains = reversed(list(make_chain(name)))
        parent = None
        for name in name_chains:
            node = Node.get_node(store, name)
            if parent:
                parent.add_child(node)
            parent = node
    return Node.get_node(store, top)


def print_tree(tree, ident=0):
    print ' ' * ident + '|%s' % tree.name
    for child in tree.children:
        print_tree(child, ident + 4)

if __name__ == '__main__':
    tree = make_tree(rs, 0)
    print_tree(tree)