Minimum number of node in AVL tree?

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