From list to tree representation

Question

Hello I have a list (in Python 3) like this :

lista=[ ['a','b','c','d'],['b','f','g'],['c','h','i'],['d'],['h'],['i'],['f'],['g']]

and I'm trying to translate it in a nested list like this

['a',['b',['f'],['g']],['c',['h'],['i']],['d']]]

so it's like this tree :

              a
            / | \
          b   c  d
         /\   /\
       f  g   h i 

I thought to use a generator like this

listb = [ lista[0][0]] + [x for x in lista[1:] ]

but I don't know how to iterate recursively through the whole list. Thank you!

Answer 1

I think this should work for you:

lista=[ ['a','b','c','d'],['b','f','g'],['c','h','i'],['d'],['h'],['i'],['f'],['g']]

def tree(root, d):
    return [root] + [tree(k, d) for k in d[root]]

d = {i[0]: i[1:] for i in lista}

root = 'a'
print(tree(root, d))

which prints this out:

['a', ['b', ['f'], ['g']], ['c', ['h'], ['i']], ['d']]

Although I believe the dictionary (d) itself might serve you better.

Answer 2

def nodeinline(head, nodes):
    return [head] + [nodeinline(child, nodes) for child in nodes.get(head, [])]

def nodebyref_to_nodeinline(lst):
    head  = lst[0][0]
    nodes = {node[0]: node[1:] for node in lst}
    return nodeinline(head, nodes)

nodebyref_to_nodeinline([['a','b','c','d'],['b','f','g'],['c','h','i'],['d'],['h'],['i'],['f'],['g']])

gives

['a', ['b', ['f'], ['g']], ['c', ['h'], ['i']], ['d']]