New course! Every coder should learn Generative AI!
Try a free lesson0
Its easy,
Consider a tree of depth/height of 'L'.
Now how many nodes a complete binary tree of 'L' number of levels should have ?
Sum of count of nodes in each level:
Level 1: nodes_count = 1 = 2^(current_level - 1)
Level 2: ... = 2 = 2 ^ (current_level - 1)
Level 3: ... = 4 = 2 ^ ( current_level - 1)
.
.
.
Level L: ... = k = 2 ^ ( current_level - 1 )
Therefore, number_of_nodes at level L = k = 2 ^ ( L - 1 )
Now, use formula for sum of GP.
Formula :
S(n) = a( r^n -1) / ( r - 1 )
So, for our case :
r = 2 = growth_rate
S(H) = 1(2^L - 1)/(2 - 1)
S(H) = 2^L - 1
So, Max number of Nodes in a Complete binary tree of height L will be (2 ^ L) - 1.
Also, Height of Tree = Number of levels - 1
This implies, Number of Levels = Height of tree + 1
Thus replacing L with H + 1 where H for Height of tree.
Number of nodes = ( 2 ^ ( H + 1 ) ) - 1