[Solved]: Number of binary trees with given height

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:

1. both left and right subtrees are of height $h$. number of trees $=A_h^2$
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