Sololearn: Learn to Code
New course! Every coder should learn Generative AI!
Try a free lesson
0
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
2nd May 2020, 1:58 PM
Arvind Singh Rawat
Arvind Singh Rawat - avatar