# Number of binary trees with given height

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.

• What did you try? Where did you get stuck? What is $n$? – Yuval Filmus Aug 30 '13 at 20:55
• How do you define height? (there are two common definitions differing by $1$) – Yuval Filmus Aug 30 '13 at 21:04
• I forgot to to say number of nodes, it is $n$. – user9909 Aug 31 '13 at 9:33
• problem setter was not very precise, I think for definition of height we consider height of root to be zero – user9909 Aug 31 '13 at 9:42
• this might help you: stackoverflow.com/a/13093274/550393 – 2cupsOfTech Apr 10 '14 at 15:44

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

• I think this is the right answer, but can we get a closed form ? – user9909 Aug 31 '13 at 9:46
• This is not the exact anwer to the question, since it does not restrict the number of nodes to $n$. By the way, for a closed form look at A001699 – Parham Sep 1 '13 at 0:20

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$.

• what is $A^{i} _{j}$ and what does $i$ stands for? – user9909 Aug 31 '13 at 9:40
• as I said, It was a test question, and the correct answer was $2^h \choose n - 2^h +1$ can you explain this ? – user9909 Aug 31 '13 at 9:50
• The author of the question must have had a different definition of binary trees in mind. The link agrees with me that $A_h - A_{h-1}$ is the number of binary trees of height $h$. – Yuval Filmus Aug 31 '13 at 14:34