251 views
0 votes
0 votes
The number of distinct BSTs that can be drawn having the same inorder traversal of tree as 6,12,20,32,45 are........

1 Answer

Best answer
4 votes
4 votes

The following observations to be kept in mind :

a) If keys are same , then we will get the same inorder traversal for different BSTs..

b) If a tree having some root 'r' is a BST , then the subtrees of its left and right child will also be BSTs provided the subtree is non empty..

c) No of BSTs with  'k' different keys  = kth Catalan number = C(2k,k) / (k+1)

So here we have 5 distinct keys..

Hence number of BSTs :  C(10,5 ) / 6

                                =   (10.9.8.7.6) / (120.6)

                                =   42

selected by

Related questions

1 votes
1 votes
2 answers
1
rajoramanoj asked Nov 6, 2017
835 views
1 votes
1 votes
1 answer
2
Aditya asked Nov 6, 2015
371 views
1 votes
1 votes
1 answer
3
s_dr_13 asked Mar 10, 2019
2,565 views
Consider the following binary tree with root at level 0. What is the internal path length for the above tree?31142932
0 votes
0 votes
1 answer
4
K ANKITH KUMAR asked Aug 29, 2018
1,787 views
Let T (n) be the number of comparisons needed in a binary search of a list of n elements. What is the recurrence relation? Explain. 1) T(n) = T(n/2) + 22) T(n) = T(n/2) +...