- 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$

For $h = 1$, we have, number of nodes $= 2$. We could take $3$, but we require the smallest graph (a graph with smallest number of nodes) so we take $2$. It means that to create a tree with height $14 we need **at least** $24$ nodes.

So $N(1) = 2$

Now, for $h = 2$, we need to create a node with a child subtree of height $1$. This may be the right or left subtree. But since this is an AVL tree, to balance a child subtree of height let's say $Hs$, we need the other child to have a height of $Hs-1$, $Hs$ or $Hs+1$. But we take $Hs-1$ for minimal case. In simple words, a node with height $5$ must have a child with height $4 (Hs)$ and another child with height $3 (Hs-1)$. So $N(2)$ can be obtained as:

$N(2) = N(1) + (0) + 1$ ($1$ is added to count the parent node, $N(1)$ or $N(Hs)$ and $N(0)$ or $N(Hs-1)$ represent two subtrees.)

Similarly:

$N(3) = N(2) + N(1) + 1$

and generalizing:

$\mathbf{N(h) = N(h-1) + N(h-2) + 1}$

- This recursion can be graphically seen as below:

Using the above recursion, we need to find $N(8)$

$N(0) = 1$

$N(1) = 2$

$N(2) = N(1) + N(0) + 1 = 1 + 2 + 1 = 4$

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

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

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

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

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

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

So, answer for (**b)** is $88$.