search
Log In
8 votes
324 views
Ttotal number of BST's possible with 6 nodes numbered 1,2,3,4,5 and 6 having a height of 4 are ??
in DS 324 views
0
$16$ ?

2 Answers

3 votes
 
Best answer

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
0
@Habib can you mention 1-2 trees which I am missing in my solution?
2

As you mentioned if 1 is child of 6 then there will be 5 BSTs but i am getting 6 as shown below:

0

you showed 52 BSts but i am getting 54 as shown below:

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..
0
@Habib I am getting 54, can you tell me which case i am missing here?
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..:)
0
@Habib you didn't answer my question, I am getting 54 BSTs but you said 56, can you tell which case i am missing?
0
But I showed u justification regarding correctness of my solution the other way as well..
1 vote

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

0
@Manu Consider the first BST (I) .

            If we keep 4,5,6 to the left of 3. We get more 4 ways right? Similarly for the BST in the second row of your diagrams (V).
0
@Warlock how can the greater values can come in the left of 3??
0
oh I assumed they are just random nodes :P sorry
0
one such tree is rhs of root =2 is 6543 and lhs is 1
0
@prashant yes, now i will find others

Related questions

2 votes
2 answers
1
406 views
There is given a infix expression: ${\color{Red} {1}}$ $A+B\times C/\left ( \left ( D+E \right )+F\times G \right )$ While converting infix expression to postfix expression number of symbols in the stack at indicated ${\color{Red} {point-1}}$ infix expression (assume stack is initially empty) ______________ they told $5$, but is it correct? Can anyone give some explanation??
asked May 6, 2019 in DS srestha 406 views
0 votes
1 answer
2
205 views
$A)$ Rotation operation of AVL tree always preserves the inorder numbering. $B)$ If every node of BST has either $0$ or $2$ children , then searching time is $O(log n)$ Which statement is correct? Given $A)$ is correct but $B)$ is not. Plz explain how?
asked May 2, 2019 in DS srestha 205 views
0 votes
1 answer
3
327 views
Assume a Binary Search Tree is not allowed to have duplicates, there is more than one way to delete a node in the tree when the node has two children.If we resolve the situation in favor of choosing element for replacement from left substructure, then which ... too ?? If we resolve the situation in favor of choosing element for replacement from left substructure what this line exactly means?
asked Apr 30, 2019 in DS srestha 327 views
0 votes
0 answers
4
146 views
Which of the following C expressions access the (i, j)th entry of an (mn) matrix strored in column major order? n(i-1)+j m(j-1)+i m(n-j)+j n(m-i)+j
asked Dec 13, 2018 in DS Jeeva Shetty 146 views
...