CODEWITHSUNDEEP
mathbinary-search-tree
sb15
sb15

Reputation: 313

Sum of roots of binary search trees of height ≤H with N nodes

Consider all Binary Search Trees of height ≤H that can be created using the first N natural numbers. Find the sum of the roots of those Binary Search Trees.

For example, for N = 3, H = 3: There are 2 trees with 1 as root, 1 tree with 2 as root and 2 trees with 3 as root.

Hence, Sum = 2∗(1)+1∗(2)+2∗(3)=10

I am trying to solve this problem by writing a function f(n,h) which is related to f(n−1,h−1) and f(n−1,h) in some way, but unable to find the solution.

Note: All numbers [1,N] must be present in the tree and the height should be ≤H

Upvotes: 3

Views: 147

Answers (2)

sb15
sb15

Reputation: 313

Here is just a DP conversion of the above recursive algorithm.

int bottom_up_specific_height(int n,int h){
 int i,j,l;
 for(l=0;l<=h;l++){
   dp[0][l]=1;
   dp[1][l]=1;
 } 
 int s=0;
 for(i=2;i<=n;i++){
   for(j=1;j<=i;j++){
     for(l=h;l>=0;l--){
       if(l==h)
         dp[i][l]=0;
       else  
         dp[i][l]+=(dp[j-1][l+1]*dp[i-j][l+1]);
       if(l==0 && i==n) 
         s+=(j)*(dp[j-1][l+1]*dp[i-j][l+1]);
     }

   }

 }  
  return s;
}

Here complexity reduces to O(h*n^2). Is it possible to optimize it further!!

Upvotes: 1

Sumeet
Sumeet

Reputation: 8292

Ok let us start with basics.

The number of BST that can be created using first N natural numbers can be very easily calculated using the following algorithm.

natural_number compute_no_of_BST(N)
{
 if(N<=1)
  return 1;
 else
 {
  left=0,right=0,sum=0;
  for(root = 1 to N)
  {
   left = compute_no_of_BST(root-1);
   right =  compute_no_of_BST(N-root);
   sum = sum + (left*right);
  }
  return sum;
 }
}

Explanation:

The key to understand this algorithm is this:

No matter what the distinct keys are, the number of BST only depends on number of distinct keys

So, this is what we use in recursion.For the left subtree number of distinct values are root-1 and for the right subtree the number of distinct values are N-root.Also we give every key the chance of being the root using the for loop.

Now, let us handle the constraint of height H.I am assuming the height to be the number of edges from root to leaf path. This can also be handled by focusing on the above algorithm and the trick is:

We will not call the recursive function calls for height > H and for this we must keep track of the number of edges traversed from root, which initially is 0.

So that kind of narrows it down to what are new function call will look like.

natural_number compute_no_of_BST(N,H,0);

And every time we make a recursive call, we increment the third variable to indicate an edge traversal.

We will also use an extra data structure, which is an array of length N where

arr[i] = number of BST with root i+1.

Here goes the algorithm for this

natural_number compute_no_of_BST(N,H,l)
{
 if(N<=1)
  return 1;
 else
 {
  left=0,right=0,sum=0;
  for(root = 1 to N)
  {
   if(l+1<=H)
   {
    left = compute_no_of_BST(root-1,H,l+1);
    right =  compute_no_of_BST(N-root,H,l+1);
    if(l==0)
     arr[root-1] = (left*right);
   sum = sum + (left*right);
   }
  }
  return sum;
 }
}

Now sum can be easily computed as

arr[0]*1 + arr[1]*2 + ..... arr[N-1]*N.

Upvotes: 1

Related Questions