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:
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:
|
1 2 3 |
te = 2*nfle - 1 te: total edges nfle: number of the first layer edges |
Pretty much this is what we can get:
Wait, that is a list! And we needed a tree. Ok, with more fantasy, this is how our tree would look like:
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:
|
1 2 3 |
Find left children position from parent on position i: 2i+1 Find right children position from parent on position i: 2i+2 Find parent position from a child: floor((i-1)/2) |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
list_first_line = list(input().split()) list_first_line = list(map(int, list_first_line)) list_first_line.sort() known_leaves = len(list_first_line) total_leaf_size = 2**((len(list_first_line)-1).bit_length()) tree = [] tree.extend([0]*(total_leaf_size-1)) tree.extend(list_first_line) tree.extend([0]*(total_leaf_size-known_leaves)) start_at = total_leaf_size-2 while start_at>= 0: tree[start_at] = tree[2*start_at+1] + tree[2*start_at+2] start_at -= 1 print(tree) |
Enjoy it!