Sum of roots of binary search trees of height ≤H with N nodes
Consider all binary search trees of height ≤H that can be generated using the first N natural numbers. Find the sum of the roots of these 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.
Therefore Sum = 2 * (1) + 1 * (2) + 2 * (3) = 10
I'm trying to solve this problem by writing some kind of f (n, h) function related to f (n-1, h-1) and f (n-1, h) but unable to find a solution.
Note. All numbers [1, N] must be present in the tree, and the height must be ≤H
source to share
Okay, let's start with the basics.
The BST number that can be generated using the first N natural numbers can be calculated very easily 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 understanding this algorithm is the following:
Whatever the different keys are, the number of BSTs only depends on the number of individual keys
So this is what we are using in recursion. For the left subtree, the number of distinct values is root-1, and for the right subtree, the number of distinct values N-root. We also give each key a chance to be root using a for loop.
Now let's look at the height constraint H. I am assuming the height will be the number of edges from root to leaf. This can also be solved by focusing on the above algorithm and the trick is:
We will not be calling recursive function calls for height> H, and for that we have to keep track of the number of edges intersecting with the root, which is initially 0.
Thus, this type is narrowed down to what a new function call would look like.
natural_number compute_no_of_BST(N,H,0);
And every time we make a recursive call, we increment the third variable, indicating an edge traversal.
We will also use an additional data structure, which is an array of length N, where
arr[i] = number of BST with root i+1.
Here goes the algorithm for that
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 the sum can be easily calculated as
arr[0]*1 + arr[1]*2 + ..... arr[N-1]*N.
source to share
Here's just the DP transform 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 the complexity comes down to O (h * n ^ 2). Is it possible to optimize it further?
source to share