AVL Tree

Question

The minimum number of nodes in AVL tree with height 8 is ____
Consider root node at height 0,

Comments

https://gateoverflow.in/44411/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 = 8

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