Python convert list to tree representation format -

Python convert list to tree representation format -

me , friend working on simple python project. implementing prefix parallel sum algorithm in our own way.

we creating , processing binary tree weird format. convert format 1 accepted tree printing libraries/software ete2.

so, every level of tree pushed in list in way

[ [level0], [level1], ... [level i-1], [root] ]

in our format every internal list (tree's level) has number of nodes or leaves.

for instance, have input: [1, 2, 3, 4, 5]. produce next output list: [[1, 2, 3, 4], [3, 7], [10, 5], [15]]

the issue above output illustration leaves not on lastly level, included in upper level lists. makes hard process list of lists , distinguish nodes leaves , arrange them in right position.

we visualize follows:

http://i.imgur.com/bkrqnzi.png

where numbers included in parenthesis nodes , other ones leaves.

in order produce output tree, utilize 1 tree drawing library. of them expect type of format: [root, [left], [right]]

so, in our illustration our format should this:

[15, [10, [3, [1], [2]], [7, [3], [4]] ], [5] ]

because not in position @ moment rewrite whole logic of our code, looking smart way convert our weird format one.

any ideas welcome. give thanks much in advance.

you can take advantage of fact element in row r, col c of tree, left , right kid elements @ position c*2 , c*2+1 of next row, respectively, if elements exist (otherwise node leaf). set algorithms:

def normalize(tree, row=0, col=0): try: node = tree[row][col] left = normalize(tree, row+1, col*2) right = normalize(tree, row+1, col*2+1) homecoming [node, left, right] if left or right else [node] except: homecoming none # kid index not exist

example:

>>> tree = [[1, 2, 3, 4], [3, 7], [10, 5], [15]] >>> print normalize(tree[::-1]) # reverse list! [15, [10, [3, [1], [2]], [7, [3], [4]]], [5]]

python list binary-tree prefix-sum