Problem Detail: I was wondering how many binary trees we have with height of $h$ with $n$ nodes(another question is how many binary trees we have with height $ lfloor{lg (n)}rfloor$). Edit: I forgot to add the number of nodes.
Asked By : user9909
Answered By : Mahmoud A.
Take the height $h$ as the length of the longest root to leaf path. After fixing the root, we count the number in two cases:
- both left and right subtrees are of height $h$. number of trees $=A_h^2$
- only one subtree has height $h$. number of trees $=2 cdot A_h cdot (A_0+A_1+…+A_{h-1})$
$$ A_{h+1} = A_h^2 + 2 cdot A_h cdot (A_0+A_1+…+A_{h-1}) $$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14043
