# Minimal AVL Tree Recurrence

Algebra Level 3

Let $T(d)$ denote the smallest size of an AVL tree of depth $d$. Clearly $T(0) = 1$ and $T(1) = 2$

Which of the following recurrences does $T$ satisfy?

1. $T(d) = T(d-1) + T(d-2)$
2. $T(d) = T(d-1) + T(d-2) +1$
3. $T(d) = 1 + 2T(d-1)$
4. $T(d) = 2T(d-2)$
5. $T(d) = T(d/2)^2$
6. None of the above
×