### 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.

## No comments:

## Post a Comment