GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
257 views


The number of BST's possible with $6$ nodes numbered $1$,$2$,$3$,$4$,$5$ and $6$ with exactly one leaf node are .......................

OR

The number of BST's possible with $6$ nodes numbered $1$,$2$,$3$,$4$,$5$ and $6$ having a height of $5$ are ....................

asked in Programming by Active (1.4k points)  
retagged by | 257 views
Should be 2 ?
@pC,no it is 32 check my solution!
Second interpretation of the question is totally giving it away, so should be removed. The original question is a good exercise.
Exactly !

2 Answers

+10 votes
Best answer

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

answered by Veteran (11.6k points)  
edited by
its 32 not $2^{32}$ and same for $2^{16}$
Intuitively I was following the same method, if you look at my trees. Thanks for proving. +1
@pratyush, yes your method is absolutley correct but what i wanted to say is no need to write all those 32 trees to get the ans just understanding the pattern is enough.

@kapil,it was a typing mistake,Thnx
@Prajwal: I totally agree.
+3 votes

I'm getting 32. But I followed brute force method. 16 rooted on node 1 and 16 rooted on node 6.

answered by Loyal (3.3k points)  
edited by
here 1st and last node are set.

remaining 4 nodes can arrange in 4! ways.

Now, 1st and last node 1 and 6 can be arrange in 2! ways

So, total number of ways 2! X 4!

isnot it?
@srestha: that way you'll get few BSTs which have more than one leaf node. We need exactly one leaf node. I suggest you try drawing few BSTs. Start with root as node 1 and form the right skewed tree 1-2-3-4-5-6 and modify from there.

My answer can be wrong though as I have used brute force and I might miss few BSTs, but my intuition says number of BSTs rooted at 1 should be equal to number of BSTs rooted at 6
The ans 32 is correct but instead of brute force method we can try counting method,check my solution!

Related questions

0 votes
0 answers
2
asked in DS by Vishal Goyal Active (1.7k points)   | 42 views
0 votes
0 answers
3
asked in DS by Vishal Goyal Active (1.7k points)   | 45 views


Top Users Jun 2017
  1. Bikram

    3912 Points

  2. Arnab Bhadra

    1550 Points

  3. Hemant Parihar

    1502 Points

  4. Niraj Singh 2

    1501 Points

  5. Debashish Deka

    1480 Points

  6. junaid ahmad

    1432 Points

  7. pawan kumarln

    1366 Points

  8. Arjun

    1246 Points

  9. Rupendra Choudhary

    1242 Points

  10. rahul sharma 5

    1240 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 26 - Jul 02
  1. pawan kumarln

    498 Points

  2. akankshadewangan24

    404 Points

  3. Arjun

    286 Points

  4. Debashish Deka

    234 Points

  5. Abhisek Das

    230 Points


23,435 questions
30,153 answers
67,633 comments
28,503 users