what is maximum possible number of binary trees for height (or depth) h

Question

Is there any closed form formula to find out maximum possible binary trees with height or depth 'h'. I have seen formula for total number of binary trees for a given number of nodes. But I have not seen any closed form formula for a given fixed height or depth irrespective of number of nodes.

Answer 1

Let's employ a recurrence relation in order to find a formula. Let n[h] be the number of binary trees with height h. Then we know that

n[0] = 1   //An empty tree
n[1] = 1   //A single leaf

A binary tree of height i can be built as follows: Either we use a tree of height i - 1 as the left child. Then we can choose any tree with height from 0 through i - 1 as the right child. Or we choose a tree of height i - 1 as the right child. Then we can choose any tree with height from 0 through i-2 as the left child (note the -2 in the last term to avoid counting the same trees twice). Hence,

n[h + 1] = Sum{i from 0 to h}[n[h]*n[i]] + Sum{i from 0 to h-1}[n[h]*n[i]]

We can calculate the first few elements:

1
1
3
21
651
457653
210065930571
44127887745696109598901
1947270476915296449559659317606103024276803403

If we search for this sequence in OEIS, we find this sequence. There are some formulas at the bottom and none of them looks to have a closed form. But that doesn't seem necessary. The sequence grows so fast that the numbers exceed fixed length data types very soon. Hence, it is very easy to calculate these few numbers that can be represented with your desired data type via dynamic programming or even pre-calculate the numbers and use them as constants.