952 views
8 votes
8 votes
Ttotal number of BST's possible with 6 nodes numbered 1,2,3,4,5 and 6 having a height of 4 are ??

2 Answers

Best answer
3 votes
3 votes

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..

 

selected by
1 votes
1 votes

I am getting only such 8 Binary Search tress when then height of a BST is restricted to 4.

Related questions

0 votes
0 votes
1 answer
2
kickassakash asked Jul 4, 2023
395 views
I have specific doubt on this question and I’ve tried to explain that in the picture ,If anyone can explain it then it’ll be of great help. according to sachin sir th...
0 votes
0 votes
1 answer
3
Souvik33 asked Apr 2, 2023
410 views
There are Insert and Retrieve_Max operations on a set {}. for n such operations what is the time complexity of the efficient algorithm possible?$n^{2}$nlogn n logn
0 votes
0 votes
1 answer
4
Souvik33 asked Nov 2, 2022
840 views
Which data structure would be most appropriate to implement a collection of values with the following 3 characteristicsSingly link list with head and tail pointerDoubly l...