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

Question

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!

Answer 1

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!