What is the minimum number of nodes (sparsest possible AVL tree) an AVL tree of height h can have ?
| Fh| = | Fh - 1| + | Fh - 2| + 1
| Fh| + 1 = (| Fh - 1| + 1) + (| Fh - 2| + 1)
| Fh| + 1 $\displaystyle \approx$ $\displaystyle {\frac{1}{\sqrt{5}}}$ $\displaystyle \left(\vphantom{\frac{1+\sqrt{5}}{2}}\right.$ $\displaystyle {\frac{1+\sqrt{5}}{2}}$ $\displaystyle \left.\vphantom{\frac{1+\sqrt{5}}{2}}\right)^{h+3}_{}$
$ \Rightarrow$
$h \approx 1.44 \log| Fn|$
$ \Rightarrow$
The sparsest possible AVL tree with n nodes has height
$$h \displaystyle \approx 1.44\log n$$
$ \Rightarrow$
The worst case height of an AVL tree with n nodes is
$$1.44\log n$$
B is the correct answer
