Here one thing to keep in mind :
With n distinct keys , the number of BSTs having height (n-1) = 2n-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..