Binary Tree -- N Nodes & H Height

The problem:

You are told that you have N unique numbers, how many different binary trees are possible with those N numbers (i.e. nodes) which has exactly H height.

Analysis:

If we look closely, it will be not that hard to figure out that, the problem actually wants to know, how many different binary trees are possible to build with N nodes, each of which has exactly H height allowing rotations. Here, two trees are different when their structures are different. For example:

           @                   @
          / \                 / \
         @   @      and      @   @
        / \                     / \
       @   @                   @   @

Solution:

I don't know whether this problem has a mathematical solution or not, I have searched for it and found nothing... But, if the values N and H supports, this problem can be solved with a dynamic programming approach.

When we want to build a tree with N nodes and H height, we can select a node as a root, so, we can put 1 to N-2 nodes on the left subtree of height H-1 or less and N-2 to 1 nodes on the right subtree of height H-1 or less, satisfying that, at least one of the subtree has a height H-1. So, by using proper base condition, we can find the number of different trees of exactly H height from this recursive formulation, and we can express the relation as follows,

if k == 1 then exactTrees( N, D ) = ( n == 1 )
if n <= 1 then exactTrees( N, D ) = 0
for all {L, R} such that L, R > 0 and L + R = N - 1:
exactTrees( N, D ) += exactTrees( L, D - 1 ) * exactTrees( R, D - 1 )
exactTrees( N, D ) += smallerTrees( L, D - 2 ) * exactTrees( R, D - 1 )
exactTrees( N, D ) += exactTrees( L, D - 1 ) * smallerTrees( R, D - 2 )

This is pretty obvious, because, if we want to get a tree of height H from any node, either one or both of its subtrees must have a height H - 1, and if we have N nodes at any step, we need to take 1 node as root, and then if we take i nodes for left subtree, we have N - 1 - i nodes left for the right subtree.
When we calculate exact height, we need to consider that a subtree may have a smaller height, so we need to calculate smallerTrees( N, D ) separately, but actually it is a bit easier:

if n < 0 or k <= 0 then smallerTrees( N, D ) = 0
if k == 1 then smallerTrees( N, D ) = ( n == 1 )
if n <= 1 then smallerTrees( N, D ) = 1
else
for all {L, R} such that L, R > 0 and L + R = N - 1:
smallerTrees( N, D ) += smallerTrees( L, D - 1 ) * smallerTrees( R, D - 1 )

Sample program:

First one goes the recursive algorithm (with dp):

// states: nodes, height
int exact[202][101], smaller[202][101];

int smallTrees(int n, int k)
{
    if(n<0 || k<=0) return 0;
    if(k==1) return n==1;
    if(n<=1) return 1;
 
    int &ret = smaller[n][k], l, r;
    if(ret!=-1) return ret;
 
    ret = 0;
    for(int i=1; i<n-1; i++)
    {
        l = i, r = n-1-i;
        if(l && r)
        {
            ret += smallTrees(l, k-1)*smallTrees(r, k-1);
        }
    }
    return ret;
}

int exactTrees(int n, int k)
{
    if(k==1) return n==1;
    if(n<=1) return 0;

    int &ret = exact[n][k], l, r;
    if(ret!=-1) return ret;
    ret = 0;
    for(int i=1; i<n-1; i++)
    {
        l = i, r = n-1-i;
        if(l && r)
        {
            ret += exactTrees(l, k-1)*exactTrees(r, k-1);
            ret += exactTrees(l, k-1)*smallTrees(r, k-2);
            ret += smallTrees(l, k-2)*exactTrees(r, k-1);
        }
    }
    return ret;
}

Here is the iterative version (a little complex):

// states: height, nodes
int exactTrees[101][202], smallTrees[101][202];

void solve(int n, int k)
{
    int d, i, j;
    exactTrees[1][1] = 1;
    for(d=2; d<=k; d++) // depth
    {
        for(i=1; i<=n; i+=2) // number of nodes
        {
            for(j=1; j<=i-1; j+=2) // left & right
            {
                exactTrees[d][i] += exactTrees[d-1][j]*exactTrees[d-1][i-1-j];
                exactTrees[d][i] += exactTrees[d-1][j]*smallTrees[d-2][i-1-j];
                exactTrees[d][i] += smallTrees[d-2][j]*exactTrees[d-1][i-1-j];
            }
        }
        for(i=1; i<=n; i+=2) // update smaller tree
        {
            smallTrees[d-1][i] += smallTrees[d-2][i]+exactTrees[d-1][i];
        }
    }
}

[P.S. The result of this problem grows very rapidly along with the increase of N and H, so, it may easily run out of range, normally problems like this requires the result with respect to some modulus values.]

Similar problem:

USACO Section: 2.3, Problem: Cow Pedigrees, Code: nocows.
[P.S. Links won't work for usaco, you need to reach level 2.3 if you want to see the problem yourself.]
If you find any more problem regarding this, please post it as a comment below.