Me and my friend are working on a simple Python project. Actually we are implementing the prefix parallel sum algorithm in our own way.
We are creating and processing a binary tree with a really weird format. We would like to convert this format to one that is accepted by Tree printing libraries/software like ete2.
So, every level of the tree is pushed in a list in that way
[ [level0], [level1], ... [level i-1], [root] ]
In our format every internal list (tree's level) has even number of nodes or leaves.
For instance, say we have this input: [1, 2, 3, 4, 5]. This will produce the following output list: [[1, 2, 3, 4], [3, 7], [10, 5], [15]]
The issue with the above output example is that sometimes leaves are not on the last level, but they are included in upper level lists. This makes it hard to process the list of lists and distinguish nodes from leaves and also arrange them in the correct position.
We would like to visualize this as follows:
https://i.sstatic.net/vWztP.png
where numbers included in parenthesis are nodes and the other ones leaves.
In order to produce this output tree, we would like to use one Tree drawing library. Most of them expect this type of format: [root, [left], [right]]
So, in our example our format should be something like this:
[15, [10, [3, [1], [2]], [7, [3], [4]] ], [5] ]
Because we are not in a position at the moment to rewrite the whole logic of our code, we are looking for a smart way convert our weird format into that one.
Any ideas are welcome. Thank you very much in advance.
You can take advantage of the fact that for the element in row r, col c of your tree, the left and right child elements are at position c*2 and c*2+1 of the next row, respectively, if those elements exist (otherwise that node is a leaf). Just put that into an 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)
return [node, left, right] if left or right else [node]
except:
return None # child index does not exist
Example:
>>> tree = [[1, 2, 3, 4], [3, 7], [10, 5], [15]]
>>> print normalize(tree[::-1]) # reverse the list!
[15, [10, [3, [1], [2]], [7, [3], [4]]], [5]]