问题描述:

Dealing with balanced and unbalanced binary trees.

`height = 0, possible trees = 1 (nothing)`

height = 1, possible trees = 1 (leaf)

height = 2, possible trees = 3

I'm looking at the Catalan function but it has not lead me anywhere beneficial, mostly because I think it might be counting trees less than height h. For example, if height it 2, it will count height 1 too (and maybe height 0) I believe.

You appear to be looking for integer sequence A001699, "Number of binary trees of height n". One possible algorithm to generate them being:

a(n+1) = 2*a(n)*(a(0)+...+a(n-1))+a(n)^2

Unfortunately, there doesn't seem to be a closed-form version. Each formula is itself recursive, or uses A003095, which is also recursive.