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.
