GATE IT 2008 | Question: 73

Question

How many distinct BSTs can be constructed with $3$ distinct keys?

• A. $4$
• B. $5$
• C. $6$
• D. $9$

Comments

@Shaik Masthan Sir in below question we are not trying to change the structure of the binary tree so 1 BST is possible right. I found this and below question related so asked.

https://gateoverflow.in/2131/gate-cse-2011-question-29#a_list

---

@Rohit Pol,

Yes. We are not allowed to change the structure of binary tree. We may change the numbers inside that. But to make it BST, we have only one sequence. 

---

Understood sir!

Answer 1

For number of distinct BSTs with $n$ nodes we apply the formula

$\dfrac{C(2n,n) }{n+1}$

$n=3$ here, so $C(6,3)=20$

So, $\frac{C(2n,n)}{n+1} =20/4=5$

Answer is $\mathbf{5}$

REF :- https://gatecse.in/number-of-binary-trees-possible-with-n-nodes/

Correct Answer: $B$

Comments

https://gateoverflow.in/485/gate2008-62

Why can’t we solve this question in a similar way as it is solved in the above link?

---

2n!/(n-1)1n!
why thorugh this formula this question can't be solved.?

---

@Manavsinh_Mori It can be solved mate.

Answer 2

 

Option B is the answer

 

Answer 3

Option B) 5 is Correct answer

Let's solve this using Catalan number :

$$C_n = \frac{(2n)!}{(n+1)! n!}$$

here n = no. of distinct keys ; n = 3  (given in question)

 

$$C_n = \frac{(2n)!}{(n+1)! n!}$$      $$  = \frac{(2 * 3)!}{(3+1)! 3!}$$

  $$  = \frac{6!}{4! * 3!}$$       $$  = \frac{6 * 5 }{6}$$

 

$$  = 5 $$ 

   

 

                                      

 

 

Answer 4

We can solve this using the concept of Catalan Number. They given 3 distinct key.

Then, 1/n+1*(2nCn)  , n=3

=1/4*6c3

1/4 *20

=5 (Option B)

Then ans is 5