+3 votes
245 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
edited | 245 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.4k points)
edited
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
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!

0 votes
0 answers
1
0 votes
0 answers
2
+3 votes
2 answers
3