# GATE1998-21

2.2k views
1. Derive a recurrence relation for the size of the smallest AVL tree with height $h$.
2. What is the size of the smallest AVL tree with height $8$?
in DS
edited
2

Min nodes recurrence relation when height $'h'$ is given:

$T(h)=T(h-1)+T(h-2)+1$

Max nodes recurrence relation when height $'h'$ is given:

$T(h)=2T(h-1)+1$

1. Consider a function $N(h)$ which represents the smallest number of nodes $n$ for an AVL tree with height $h$ and satisfies $n = N(h)$.
For $h=0$ we have, number of nodes $= 1$. So $N(0) = 1$