I know the formula of finding minimum number of node in a AVL tree is

`S(h) = S(h-1) + S(h-2) + 1`

However, I don’t really get how to use this function, say if we have a AVL height of 6. The answer tells me that Minimum = 7 + 4 + 1 =12. But how do you get this number? I mean when you plug in 6 isn’t it (6-1) + (6-2) + 1?

Can anyone explain to me how to solve this? My teacher haven’t talk about this yet but I really want to figure this out myself in order to be prepared for the test next week.

## Answer

In `S(h) = S(h-1) + S(h-2) + 1`

,

`S(h)`

is a **recursive** function/formula. A recursive function calls itself (in a smaller or simpler way) inside its body.

Note that a recursive function must have some base cases, in this case:

S(1) = 0 S(2) = 1

So let’s say `h = 6`

, then `S(h = 6)`

will be (just replacing):

S(6) = S(6-1) + S(6-2) + 1 S(6) = S(5) + S(4) + 1 S(6) = 2*S(4) + S(3) + 1 + 1 S(6) = 2*(S(3) + S(2) + 1) + S(3) + 2 S(6) = 3*S(3) + 2*S(2) + 4 S(6) = 3*(S(2) + S(1) + 1) + 2*S(2) + 4 S(6) = 5*S(2) + 3*S(1) + 7 S(6) = 5*1 + 3*0 + 7 S(6) = 12