Python – Build a binary tree list in python

Binary trees are really useful, if you are solving an algorithmic problem. They consists of nodes (a.k.a vertices) and edges. Thus, each node has two edges, which are leading to another node. Something like this:

300px-Binary_tree.svg

The above tree is a simple random non-balanced tree, taken from Wikipedia. In the current article, I will show how to build a balanced binary tree from given “leaves”. The leaves are the nodes on the first level.

The idea, behind our tree, is that each node would be the sum of the previous two nodes and thus until the end.

So, lets imagine that we have as entry the following numbers: 1,2,3,3,4,10. These are the numbers, that we would be using the first level of our tree. In order to make a balanced tree, the rule is that we should have first layer which is part of the binary sequence. Thus, in our occasion, we should enlarge the layer, by adding two more values to the right, in order to reach 8, because the count of the values was 6. Once we have done that, we could start building the other layers, using the following formula:

Pretty much this is what we can get:

tree_list

Wait, that is a list! And we needed a tree. Ok, with more fantasy, this is how our tree would look like:

tree

The first element of the list is the root, the second and the third are its children and the 4th, 5th, 6th and 7th  are his grandchildren. Easy as that. The good thing is that it is easy to find the parent-child relationship once we have a tree built-in with the following formulas:

So that is all. Here comes the code in python, which can make a binary tree list from numbers, following the rule that every parent is the sum of its children.

Enjoy it!

About

VBA Developer

Tagged with: , ,