GATEBOOK exam

Question

Maximum height an AVL tree can have with 77 nodes

(A) 8

(B) 9

(C) 6

(D) 7

Answer 1

Answer : (D) 7

We know the recursive formula for finding minimum number of nodes required to construct an AVL tree of height h is :

N(h) = 1 + N(h-1) + N(h-2) ;

N(0) = 1; N(1) = 2;

If you solve above equation, you will get

N(7) = 54 & N(8) = 88

This means that minimum 88 nodes are required to construct AVL tree of height 8. So with the given 77 nodes we can construct AVL tree of maximum height 7.