How many binary trees of minimal height are there for a given number of nodes?

Question

A binary tree has minimal height if the distance from the root to any point is minimal over all trees (with the same number of nodes). How many trees of minimal height are there? I tried finding this sequence in OEIS with no luck. Clearly for $n = 2^k - 1$ the answer is $1$. I'm also interested in recurrence relations for this number.

Ex. For $n = 4$ there exist $6$ possible trees. $4$ configurations where there are $3$ "top" nodes and $1$ bottom, and $2$ configurations purely on the left/right side of the root.

Answer 1

Let's call the function you're looking for $f$. Then we already know that: $f(2^k-1) = 1$ for any $k \in \mathbb{N}$. This correspond to a full binary tree of depth $k$.

Let's also state that $f(0) = 1$, as there is a unique way to create an empty tree ($0$ nodes).

We will now try to find a recurrence relation.

Assume we already know all values of $f(n), \forall n \in \{0, \ldots, 2^k-1 \}$ .

Let's try to compute the value of $f(2^k-1+p)$ for $0 < p < 2^k$.

What happens when adding a $p$ nodes to a minimal tree of $2^k-1$ nodes ? Obviously the depth of the tree must increase. As we are looking for minimal depth trees, it should only increase by $1$. This is because the depth of a minimal tree of $2^{k+1}-1$ nodes is $k+1$ so by removing nodes from such a tree we can create a minimal depth tree of $2^k-1+p$ nodes.

Knowing the new depth we can find a first tree structure:

A 2^k-1+p nodes tree

                      [root]
                      /    \
[2^k-1 nodes sub-tree]      [p-1 nodes sub-tree]

Which is a tree made of a root node, a left sub-tree of size $2^k-1$ and a right sub-tree of size $p-1$. We have $f(2^k-1) \cdot f(p-1)$ ways of creating such tree, $f(2^k-1)$ ways of creating the left sub-tree and $f(p-1)$ ways of creating the right sub-tree.

Now we can create all other tree structures by moving nodes from the left to the right, until we reach the situation where we have only $p-1$ nodes on the left and $ 2^k-1$ nodes on the right.

This means we have:

$$ \begin{align*} f(2^k-1+p) &= f(2^k-1 - 0) \cdot f(p-1 + 0) \\ &+ f(2^k-1 - 1) \cdot f(p-1 + 1) \\ &+ \ldots \\ &+ f(2^k-1 - (2^k-1-(p-1))) \cdot f(p-1 + (2^k-1-(p-1))) \end{align*} $$

Which simplifies as:

$$ f(2^k-1+p) = \sum_{i=0}^{2^k-p}{f(2^k-1-i) \cdot f(p-1+i)} $$

Please note that this is not a usual recurrence relation as you need to first determine $k$ the depth of the tree before applying the formula.