# 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