## Wednesday, August 4, 2010

### 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 ) = 0for 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 ) = 0if k == 1 then smallerTrees( N, D ) = ( n == 1 )if n <= 1 then smallerTrees( N, D ) = 1elsefor 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, heightint 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, nodesint 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.