GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
282 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.5k points) 5 14 50
retagged by | 282 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 (12.5k points) 10 47 90
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 (4k points) 6 12 27
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

+1 vote
2 answers
1
asked in Programming by rahul sharma 5 Veteran (14.9k points) 12 103 309 | 65 views
0 votes
0 answers
3
asked in DS by Vishal Goyal Active (2.2k points) 2 18 36 | 50 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23240 Points

  2. Bikram

    17038 Points

  3. Habibkhan

    7096 Points

  4. srestha

    6008 Points

  5. Debashish Deka

    5430 Points

  6. jothee

    4928 Points

  7. Sachin Mittal 1

    4762 Points

  8. joshi_nitish

    4278 Points

  9. sushmita

    3954 Points

  10. Rishi yadav

    3744 Points


Recent Badges

Notable Question tajar
Notable Question Imarati Gupta
Notable Question set2018
Popular Question jothee
Notable Question set2018
Notable Question Pavan Kumar Munnam
Notable Question iarnav
Popular Question makhdoom ghaya
Popular Question Satyam
Popular Question radha gogia
27,254 questions
35,075 answers
83,756 comments
33,185 users