Number of binary trees with given height

Question

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.

Answer 1

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}) $$

Answer 2

I assume that a binary tree is given by the following specification: a binary tree is either (a) empty or (b) is composed of a root and two (ordered) subtrees.

I also assume that height is defined so that a complete binary tree of height $h$ has $2^{h+1}-1$ nodes (for example, a single node has height $0$).

Let $A_h$ be the number of binary trees with height at most $h$. Then $A_{-1} = 1$ and $A_h = 1 + A_{h-1}^2$. This is A003095. The number of trees with height exactly $h$ is $A_h - A_{h-1}$, which is A001699. Both sequences have asymptotics of the form $\alpha^{2^h}$ for some $\alpha > 1$.