Number of distinct Binary tree formed with respect to height h

Question

How many types of distinct Binary Tree can be formed with a height of h? assuming height starts from 0 when the tree has only the root. example: if the height of tree is 1 then
root-leftchild
root-rightchild
root-leftchild-rightchild are the possible trees with height 1

Answer 1

This can be solved recursively. Let $T_n$ be the number of trees of height $n$. So $T_0 = 0$ and $T_1 = 3$ are easy to see.

Also let $S_n$ be the number of trees of height from $1$ to $n$.

So $T_n = S_n - S_{n-1}$.

Counting $S_n$ is a little easier than $T_n$ so we do that.

To list/draw the trees for $S_{n+1}$ (i.e. all trees with height up to $n+1$), we can start at the top with a left branch and hanging off it we can put any of the $S_n$ trees having height up to $n$. There are also two other options for the left side: just the single left branch alone and also no left branch at all. So the left side has $S_n + 2$ choices. For each of these left-side choices, we have the same $S_n + 2$ choices on the right-hand side. The only exception is that both sides can't be empty (assuming we don't count the empty tree). Combining the left and right choices by simple multiplication and subtracting $1$ for the empty tree, we have:

\begin{eqnarray*} S_{n+1} &=& \left(S_n + 2\right)^2 - 1 \\ &=& S_n^2 + 4S_n + 3 \end{eqnarray*}

Quadratic recurrence relations, which this is, generally have no "closed form" solution, unfortunately.

But if your purpose is more practical than theoretical, that might not be important because the recurrence relation allows you to calculate the value of $S_n$ and then $T_n$ from $1$ up to whatever number you choose. The first few values:

\begin{eqnarray*} n && S_n && T_n \\ 1 && 3 && 3 \\ 2 && 24 && 21 \\ 3 && 675 && 651 \\ 4 && 458328 && 457653 \\ 5 && 210066388899 && 210065930571 \end{eqnarray*}