Possible distinct binary tree structures at depth d

Question

I'm trying to figure out a recursive formula for the number of possible distinct binary trees at any depth d. I haven't been able to find any sort of sources on this.

basically, at depth 0, the only binary tree is the empty one so 0, 1

then at depth 1 the only possibility is a single node so 1, 1

at depth = 2 there are 3 possibilities, and at depth 3 I counted 21 possibilities.

I haven't been able to figure out some recursive reasoning for what 4 could be and so on. The only thing I have in place is that there will always be 1 for the full tree.

Answer 1

Let $D_n$ be the number of distinct binary trees with depth $n$.
Let $L_n = \sum_0^n D_k$ be the number of distinct binary trees with length $n$ or less.

Then $D_n = 2 \cdot D_{n-1} \cdot L_{n-2} + D_{n-1}^2$

The first term counts the number of uneven trees (left subtree has different depth than right subtree) and the second term counts the number of even trees (left subtree has same depth as right subtree).

Answer 2

If $T$ with root $r$ has depth $d+1$, at least one of the two subtrees at $r$ must have depth $d$. Thus, if $a_n$ is the number of trees with depth $n$, then

$$a_{d+1}=2a_d\sum_{k=0}^{d-1}a_k+a_d^2=\sum_{k=0}^da_ka_d+\sum_{k=0}^{d-1}a_ka_d\;.$$

Let $b_d=\sum_{k=0}^da_k$; then $a_0=b_0=1$, and we have the recurrences

$$\left\{\begin{align*} a_{d+1}&=a_d(b_d+b_{d-1})\\ b_{d+1}&=b_d+a_{d+1}\;. \end{align*}\right.$$

At this point some numerical evidence would be useful:

$$\begin{array}{rcc} d:&0&1&2&3&4\\ a_d:&1&1&3&21&651\\ b_d:&1&2&5&26&677 \end{array}$$

Note that $a_3=21$, not $16$. We can now check OEIS, and it turns out that $\langle a_n:n\in\Bbb N\rangle$ is there: it’s OEIS A$001699$. There are references and a recurrence, but no closed form is given. There is a comment noting that it approaches $c^{2^n}$, where $c=1.5028368\ldots\;$.

The sequence $\langle b_n:n\in\Bbb N\rangle$ is nicer: the data suggest that $b_{n+1}=b_n^2+1$, and indeed this turns out to be the case. The proof is easy: to get a tree of depth at most $n+1$, pick two trees of length at most $n$ and make them the left and right subtrees at a new root. This is OEIS A$003095$.