Let the number of binary trees with N
leaves be T(N)
.
We have T(1) = T(2) = 1
, as can be immediately seen, and for N > 2
we can split at the root, obtaining two subtrees with fewer leaves. Or, equivalently, we can assemble a binary tree with N
leaves from two non-empty binary trees with k
and N-k
leaves respectively. The condition that both subtrees are non-empty translates to 1 <= k <= N-1
. So we have the recursion
N-1
T(N) = ∑ T(k) * T(N-k)
k=1
If the recursion is not yet known, it is not difficult to compute the first few values
1,1,2,5,14,42,132,429,1430,4862,16796
and google them. One finds that these are the Catalan numbers,
C(n) = (2*n)! / (n! * (n+1)!)
offset by one, so
T(N) = C(N-1)
which can be computed much faster than the recursion.