Minimum number of nodes in balanced binary search tree

Question

I'd like to know if anyone could help me verify a recursive formula for the minimum possible number of nodes a binary search tree would require to be balanced. So far, I know that the recursive solution for the maximum possible number of nodes is $M(d)=2M(d−1)+1$, where d is the depth of the BBT. I assume that for the minimum number it may be: $M(d)=2M(d)$ as the non-recursive formula is simply $2^d$. Is this correct, or am I thinking along the wrong sort of lines?

Answer 1

Hint You want a minimum node depth $d$ balance binary search tree. What happens if you take a maximum node tree of depth $d-1$ and add a single node?