GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
271 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 | 271 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.8k 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.4k 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.9k points)   | 47 views
0 votes
0 answers
2
asked in DS by Vishal Goyal Active (1.9k points)   | 52 views


Top Users Aug 2017
  1. Bikram

    5388 Points

  2. ABKUNDAN

    4730 Points

  3. manu00x

    3582 Points

  4. akash.dinkar12

    3534 Points

  5. rahul sharma 5

    3196 Points

  6. makhdoom ghaya

    2710 Points

  7. just_bhavana

    2432 Points

  8. stblue

    2244 Points

  9. Tesla!

    2126 Points

  10. pawan kumarln

    1914 Points


25,076 questions
32,240 answers
75,170 comments
30,249 users