I have n elements like 1,2,3,4....n. I wanted to count the number of possible binary search tree with height H for all possible roots
Count number of Binary Search Tree with all possible height:
int countTrees(int N) {
if (N <=1) {
return(1);
}
else {
int sum = 0;
int left, right, root;
for (root=1; root<=N; root++) {
left = countTrees(root - 1);
right = countTrees(N - root);
// number of possible trees with this root == left*right
sum += left*right;
}
return(sum);
}
}
In the above program, I wanted to add the constraint of height H
Edit:
Example -
Input N = 3 H = 3
I don't want to count trees having a height greater than H
Total No. of tree 5
There are 2 trees with root =1, 1 tree with root =2, 2 trees with root =3
My Final answer is 10 (sum of all root node number) Thus,
answer = 1*2 + 2*1 + 3*2 = 10
You have done more than 90% of the job, allow me to do the remaining.
I have tried to keep most of the code same.
If we do not want to count the number of trees whose height exceeds given h, we simply do not call the corresponding recursive calls.
The function will be called from the main like this:
countTrees(3,2,0);
N = 3, H = 2 and 0 is the number of edges traversed on downward path from root.
The array arr in the code is of length 3 and it is global and arr[i] will give the number of trees possible with root i+1.
int countTrees(int N,int h,int l) {
if (N <=1) {
return(1);
}
else {
int sum=0;
int left, right, root;
for (root=1; root<=N; root++) {
left=0;right=0;
if(l+1<=h)
{
left = countTrees(root - 1,h,l+1);
right = countTrees(N - root,h,l+1);
if(l==0)
arr[root-1]+=left*right;
sum+=left*right;
}
}
return sum;
}
}
Check http://ideone.com/okPqj9
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println(countTrees(3, 1, 3));
}
public static int countTrees(int N, int curH, int H) {
if ( curH > H ) return 0;
if (N <=1) {
return(1);
}
else {
int sum = 0;
int left, right, root;
for (root=1; root<=N; root++) {
left = countTrees(root - 1, curH+1, H);
right = countTrees(N - root, curH+1, H);
// number of possible trees with this root == left*right
sum += left*right;
}
return(sum);
}
}
}
I do not guarantee it is correct, but the overall idea - prune all trees with height greater than H
This alg is quite slow for large N, there are faster solutions (although without H constraint): http://techieme.in/count-binary-search-trees/
the way is probably passing a third parameter to countTrees (height) and adding a condition that if h is greater than something simply return (and obviously you can increase that parameter when you call the function recursively)
