Dictionary to tree format (hopefully simple)

[John Nagle]

Diez B. Roggisch wrote:
> 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

    Not quite. That gets you

     [0, [1, [3, [4, [5, 8, [9]], 7]], 2, [6]]]

which probably isn't what you want.  Note that the children of 0 are

	1, [3, [4, [5, 8, [9]], 7]],
	2,
	[6]

which probably isn't what was desired.
You probably want

	[0, [1, [3, [4, [5], [8, [9]]], [7]]], [2, [6]]]

so that each list is [node, [children]]. 	

The original poster wanted

	[ 0 [ 1 [ 3 [ 4 [ 5 , 8 [ 9 ] ] , 7 ] ] , 2 [ 6 ]  ]

but that's not a meaningful Python list expression.

Try this recursive form:

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

def getsubtree(d, node) :
	if d.has_key(node) :
	    return([node] + [getsubtree(d,child) for child in d[node]])
	else :
	    return([node])

getsubtree(d,min(d.keys())) # smallest node is assumed to be the root
				
					John Nagle