Calculating the level of insertion based on the size of the tree

Question

If I have a graph structure that looks like the following

a         level-1 
b c       level-2
c d e     level-3
e f g h   level-4
......    level-n

a points to b and c 
b points to c and d 
c points to d and e 
and so on 

how can i calculate the n from the size(number of existing nodes) of the graph/tree?

Answer 1

The number of nodes present if the height is h is given by

1 + 2 + 3 + ... + h = h(h + 1) / 2

This means that one simple option would be to take the total number of nodes n and do a simple binary search to find the right value of h that such that h(h + 1) / 2 = n.

Alternatively, since n = h(h + 1) / 2, you can note that

n = h(h + 1) / 2

2n = h² + h

0 = h² + h - 2n

Now you have a quadratic equation (in h) that you can solve to directly get back the value of h. The solution is

h = (-1 ± √(1 + 8n)) / 2

If you take the minus branch, you'll get back a negative number, so you should take the positive branch and compute

(-1 + √(1 + 8n)) / 2

to directly get back h.

Hope this helps!