8 votes

3 votes

Best answer

Here one thing to keep in mind :

With n distinct keys , the number of BSTs having height (n-1) = 2

^{n-1}

So we have to take various cases here i.e. checking number of BSTs of height = 4 for each valid root value.. For root value = 3 and 4 , we cannot get height greater than 3 because , say for root value = 4 , we can have 3 - 2 - 1 in left in skewed fashion in worst case and 5-6 on right which leads to height of 3 only.Similar is the case for root value = 3..

As we can see the reasoning we use for root = 6(max value) can be used for root value = 1(min value) and similarly by finding number of required BSTs having root value = 5 (second max) , this will be the number of BSTs having root value = 2(second min) as well.

Here we show the steps of finding :

Hence total number of BSTs = BSTs having 6 as root node + BSTs having 1 as root node + BSTs having 5 as root node + BSTs having 2 as root node

= 2 * (BSTs having 5 as root node + BSTs having 6 as root node) ...........(1)

Number of BSTs having 5 as root node = Number of BSTs having 2 as root node = 8

Number of BSTs having 6 as root node = Number of BSTs having 1 as root node = 4(having 4 as child of 6) + 4(having 2 as child of 6) + 6(having 1 as child of 6) + 6(having 5 as child of 6) = 20

Hence total number of BSTs with given 6 keys and height of 4 = 2 * (BSTs having 5 as root node + BSTs having 6 as root node)

= 2 * (8 + 20)

= 56

**Hence required number of BSTs of height 4 should be 56..**

*Alternative method( For verification purpose) : *

Given n nodes and h as height of the BST , let b(h,n) be the number of such BSTs upto height 'h' and 'n' nodes ..Then b(h,n) is given by the following recurrence relation :

b(h,n) = β b(h-1 , i-1) * b(h-1 , n - i) where i varies from 1 to n..The base cases being b(0,0) = b(0,1) = 1 and b(0,k) = 0 , b(k ,0) = 1 for any value of k > 1 ..

The above recurrence , as mentioned earlier is calculative and hence it is mentioned here for correctness of above solution only..So here we compute the values of b(h,n) using a dynamic programming solution as below :

**#include<stdio.h>**

**int main() {
int arr[10][10],i,j,k;
arr[0][0] = arr[0][1] = 1;
for(i = 1 ; i < 10 ; i++)
arr[i][0] = 1;
for(i = 2 ; i < 10 ; i++)
arr[0][i] = 0;
for(i = 1 ; i < 10 ; i++)
{
for(j = 1 ; j < 10 ; j++)
arr[i][j] = 0;
}
for(i = 1 ; i < 10 ; i++)
{
for(j = 1 ; j <= 6 ; j++)
{
for(k = 1 ; k <= j ; k++)
arr[i][j] = arr[i][j] + (arr[i-1][k-1]*arr[i-1][j-k]);
}
}
printf("%d\n",arr[4][6]);
return 0;
}**

Here arr[i][j] is denoting number of BSTs upto height i and no of nodes as j..So arr[4][6] returns number of BSTs having 6 nodes and height upto 4 and similarly arr[3][6] returns number of BSTs having height upto 3 and having 6 nodes as well..

On executing the above program , we get arr[4][6] = 100 and arr[3][6] = 44..

Hence number of BSTs of 6 nodes having height of 4 = arr[4][6] - arr[3][6]

= 100 - 44

= 56

**Hence this way also it is verified that the number of BSTs of height 4 and 6 nodes = 56.Hence 56 should be correct..**

** **

0

No of trees having 6 as root and 1 as its child becomes 6 [ I missed the case in which 2 is a child of 1 ; now corrected ] , so the same way now no of BSTs having 6 as root and 5 as child of 6 wil become = 6 BSTs as well instead of 5..

Hence in total 4 more BSTs we will get..Hence 56 should be correct..

Hence in total 4 more BSTs we will get..Hence 56 should be correct..

0

I am astonished that this question has not that much views..Though I must admit it is one of the few questions which I appreciate for asking.I really liked it solving..:)