Dictionary to tree format (hopefully simple)

[Diez B. Roggisch]

Adam Powell schrieb:
> Hi!
> I have seemingly simple problem, which no doubt someone out there has
> already solved, but I'm stumped. Imagine I have a dictionary like
> below, in which the keys are parent nodes and the values are a list of
> children nodes.
> 
> dict = { 0: [1, 2], 1: [3], 2: [6], 3: [4,7], 4: [5,8], 8: [9] }
> 
> Is there an obvious way to produce a nested tree format for this
> dictionary, like this:
> 
> [ 0 [ 1 [ 3 [ 4 [ 5 , 8 [ 9 ] ] , 7 ] ] , 2 [ 6 ]  ]
> 
> Thanks for any help,

d = { 0: [1, 2], 1: [3], 2: [6], 3: [4,7], 4: [5,8], 8: [9] }

nodelists = dict((node ,[node, []]) for node in d.keys())

for node, children in d.iteritems():
     for child in children:
         nodelists[node][1].extend(nodelists.setdefault(child, [child]))

print nodelists[0]


Two remarks:

  - don't use "dict" as name for a dictionary - look at the above code 
*why* not...

  - the code assumes that 0 is the root. if that wouldn't be the case, 
you need to search for the root node. I've got an idea - you to?

Diez