recategorized by
3,181 views
3 votes
3 votes
The number of BST possible with 6 nodes numbered 1, 2, 3, 4, 5 and 6 with exactly one leaf node __________
recategorized by

1 Answer

Best answer
9 votes
9 votes

The ans is 25=32

Here the elements are  1,2,3,4,5,6 and we need only 1 leaf 

1.So let us fix a root node: To fix the root node we have 2 choice either 1 or 6 from  1,2,3,4,5,6

(if we select any non-extreme elements then only 1 leaf is not possible)

Let us say we select 1 as root node 

2.In each and every level we have 2 different option that is to select i,e; either of extreme elements

So in 2nd level we can select 2,3,4,5,6

Let us say we select 6 in 2nd level 

3.We still have 2 option to select in 2,3,4,5

So this is true in all levels except last level since only 1 element is left.

Therefore, total possibilities are : 2 * 2 * 2 * 2 = 24

The same condition is true for 6 as a root

Hence, 24* 2 (1 as root or 6 as root)  =  25

For more info refer the link below
https://gateoverflow.in/101761/data-strucutre

I hope it helps you. This ques was recently asked here only. :)

selected by

Related questions

1 votes
1 votes
2 answers
1
rajoramanoj asked Nov 6, 2017
837 views
1 votes
1 votes
1 answer
2
shreshtha5 asked Nov 30, 2015
558 views
certain file system stores records as per binary search tree principles.If the preorder traversal is 90,40,30,190,140,100,290.What is the expected number of comparisons w...
0 votes
0 votes
1 answer
3
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) +...
1 votes
1 votes
1 answer
4
Aditya asked Nov 6, 2015
372 views