GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
251 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.3k points)  
edited by | 251 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.5k 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
1
asked in DS by Vishal Goyal Active (1.1k points)   | 41 views
0 votes
0 answers
2
asked in DS by Vishal Goyal Active (1.1k points)   | 42 views


Top Users May 2017
  1. akash.dinkar12

    3292 Points

  2. pawan kumarln

    1652 Points

  3. sh!va

    1650 Points

  4. Arjun

    1424 Points

  5. Bikram

    1372 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1142 Points

  8. Angkit

    1044 Points

  9. LeenSharma

    904 Points

  10. srestha

    718 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    458 Points

  2. Arnab Bhadra

    402 Points

  3. pawan kumarln

    278 Points

  4. Ahwan

    236 Points

  5. bharti

    194 Points


22,786 questions
29,121 answers
65,184 comments
27,661 users