Question

Find the minimum no of nodes in an avl tree of height 9?

Answer 1

The minimum number of nodes in an AVL tree for a tree with a height h. The following equation is the recursive call of the N(h) function. formula N(h)=1+N(h-1)+N(h-2) Since we know that N(0)=1 ,N(1) = 2, N(2) = 4

Since h = 9

N(3)= 1+ N(2)+N(1)= 1+2+4=7

N(4) = 1+N(3)+N(2)=1+7+4=12

N(5)= 1+N(4)+N(3)= 1+12+7=20

N(6)=1+N(5)+N(4)= 1+20+12= 33

N(7)=N(6)+N(5)+1= 1+33+20=54

N(8)=1+N(7)+N(6)= 1+54+33=88

N(9) = 1 + N(8)+N(7) = 1+88+54=143