1
$\begingroup$

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

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?

pic. 2

If yes, what is the formulas? Thank you!

$\endgroup$

1 Answer 1

1
$\begingroup$

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!

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.