MadeEasy Subject Test: Programming & DS - Binary Search Tree

Question

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 )

Comments

Exactly !

---

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

---

@Shaik Masthan

In this question BST also like chain ,right?  https://gateoverflow.in/3462/gate2007-it-29

Then why in this question searching procedure is different?

Answer 1

The ans is 2⁵=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 = 2⁴

The same condition is true for 6 as a root

Hence, 2⁴* 2 (1 as root or 6 as root)  =  2⁵

Comments

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.

Answer 2

I'm getting 32. But I followed brute force method. 16 rooted on node 1 and 16 rooted on node 6.

Comments

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!