Looking for formulas to create a virtual binary tree from a simple list with an incremental index [closed]

I have a task to make data structure like a binary tree (pic. 1).

Where each node has only two child nodes, for each node I should may get its nesting level, and for every two nodes, I can get the distance between them vertically. new nodes inserts into structure left to right from top to bottom for each level of structure. And for each node, I should get a level count that is filled level.

Can I create just a list of elements: 0,1,2,3,..,n (pic. 2), and for any index get his vertical level, number in the order in horizontal level through formulas?

If yes, what is the formulas? Thank you!

The number of nodes of each row of your tree is $$2^d$$ where d is the depth, and the first row is $$d=0$$. The number of nodes up to and including row $$d$$ is $$2^{d+1}$$. The inverse of $$2^n$$ is $$\log_2 n$$.

If you have node $$n$$ then its depth the smallest $$d$$ such that $$2^{d+1} \le n$$, which is $$\lfloor \log_2 (n+1) \rfloor$$. Using Python, your nodes 6 and 10 are at depths:

>>> import math
>>> math.floor(math.log2(6+1))
2
>>> math.floor(math.log2(10+1))
3


and more programmatically:

>>> for i in range(15):
...   print(i, math.floor(math.log2(i+1)))
0 0
1 1
2 1
3 2
4 2
5 2
6 2
7 3
8 3
9 3
10 3
11 3
12 3
13 3
14 3


Another way to think about your nodes is via their binary representation, though in this case you should start from 1:

i i+1 bin(i+1)
0 1 0001
1 2 0010
2 3 0011
3 4 0100
4 5 0101
5 6 0110
6 7 0111
7 8 1000
8 9 1001
9 10 1010
10 11 1011
11 12 1100
12 13 1101
13 14 1110
14 15 1111

The depth is the position of the left-most '1' in the binary representation (That's what $$\lfloor\log_2(n+1)\rfloor$$ computes). Your node 9, for example, corresponding to the binary representation for 10, which i "1010". The left-most '1' is 3 positions to the left, so it's at depth 3.

Furthermore, the binary representation let lets you know how to find it: a "0" means go left and a "1" means go right. For example, the binary representation for your 13 is bin(13+1) = "1110". Start from the left-most "1". The rest of the pattern is "110". This means "right-right-left".

Go from the top of your tree (the 0), then right (on 2) then right (on 6) then left (on 13). Ta-da!

• Thank you very much! Feb 3 at 12:50
• Hello! Can I get parent and child of each node by formula? Apr 28 at 6:02