OT: Binary tree logarithms properties

[Terry Reedy]

Mr.SpOOn wrote:
> Hi,
> I'm searching for a clear explanation of binary tree properties,
> expecially the ones related to logarithms.
> 
> For example, I know that in a tree with 2n-1 nodes, we have log(n)
> levels, from 0 to log(n).

A *complete* binary tree with n levels has 2**n - 1 nodes.  This is 
easily shown by induction. (Try Wikipedia for induction proof if you are 
not familiar with such.)

> So, if k is the level, the nodes on a level have indexes between 2^k
> and 2^(k+1)-1.
> 
> For k=0 we have 2 and 3.
> For k=1 we have 4, 5, 6, 7
> and so on.

Nodes only have single number indexes if you arrange them linearly. 
Then the index depends on how you arrange them, whether you start the 
array indexes with 0 or 1, and whether you start the level numbers with 
0 or 1.  Call the breadth-first sequence bf.  Then the 1-based slice for 
1-first level k is bf[2**(k-1):2**k)].  Again, proof by induction.

Terry Jan Reedy