560 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 .................…

( note :- height of a root is 0 )
in DS
recategorized | 560 views
0
Should be 2 ?
+1
@pC,no it is 32 check my solution!
0
Second interpretation of the question is totally giving it away, so should be removed. The original question is a good exercise.
0
Exactly !
0
the question is updated !

For understanding relation between second question and first question

with $n$ nodes, we can get maximum $n-1$ height where root height = 0 ===> that should be a chain

∴ No.of leaf nodes = 1

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

by Loyal
edited
+1
its 32 not $2^{32}$ and same for $2^{16}$
0
Intuitively I was following the same method, if you look at my trees. Thanks for proving. +1
+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
+1
@Prajwal: I totally agree.

I'm getting 32. But I followed brute force method. 16 rooted on node 1 and 16 rooted on node 6. by Active
edited
+1
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?
0
@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
0
The ans 32 is correct but instead of brute force method we can try counting method,check my solution!