Reconstructing a tree from lists of branches

Question

A list of lists of nodes is given where every sublist identifies a branch. The goal is to write a python program to reconstruct the tree from these branches. By "branch" I mean a list starting from the root of the tree and ending at a leaf. Let's assume the main list has this form:

branches = [b_1 , b_2 , b_3 , ... , b_n]

Here number of branches is equal to the number of leafs n. Every branch contains the list of nodes in order from the root of the tree to the leaves:

b_i = [root,n_1,n_2,n_3,...,leaf_i]

the goal is to merge all the lists into a dictionary that captures the structure of the tree. Each node should have two key-value pairs : name and children. The value of name is the name of the node and the value of the children is a list of nodes (dictionaries with name and children again). Without this particular structure, this question is very similar to How to turn a list into nested dict in Python

for example if the list is:

branches=[[root,n1,l1],[root,n1,l2],[root,n2,l3],[root,n2,l4]]

we are looking for a dict like this:

treeDict = {'name':root,'children':
              [
                {'name':n1,'children':[
                    {'name':l1,'children':[]},
                    {'name':l2,'children':[]}]},
                {'name':n2,'children':[
                    {'name':l3,'children':[]},
                    {'name':l4,'children':[]}]}
              ]
           }

which represents this tree:

        root
      /     \
     n1      n2
    /  \    /  \
   l1   l2 l3   l4

@KlausD. if I forget about the child list and and name keys, this is almost the same : stackoverflow.com/questions/7653726/… — MostafaMV

YS-L YS-L · Accepted Answer · 2014-11-05T06:18:24

This is one way of doing it using some recursion over a dict:

import pprint


def traverse(root, branch):
    if not branch:
        return
    if branch[0] not in root:
        root[branch[0]] = {}
    traverse(root[branch[0]], branch[1:])


# Or rather, uglify
def prettify(root):
    res = []
    for k, v in root.iteritems():
        d = {}
        d['name'] = k
        d['children'] = prettify(v)
        res.append(d)
    return res


d = {}
branches = [['root','n1','l1'],['root','n1','l2'],['root','n2','l3'],['root','n2','l4']]
for b in branches:
    traverse(d, b)
pprint.pprint(d)
pprint.pprint(prettify(d))

Output:

# The compact representation
{'root': {'n1': {'l1': {}, 'l2': {}}, 'n2': {'l3': {}, 'l4': {}}}}

# The desired representation
[{'children': [{'children': [{'children': [], 'name': 'l2'},
                             {'children': [], 'name': 'l1'}],
                'name': 'n1'},
               {'children': [{'children': [], 'name': 'l4'},
                             {'children': [], 'name': 'l3'}],
                'name': 'n2'}],
  'name': 'root'}]

Reconstructing a tree from lists of branches

1 Answers