GATE CSE 2005 | Question: 35

Question

How many distinct binary search trees can be created out of $4$ distinct keys?

• A. $5$
• B. $14$
• C. $24$
• D. $42$

Comments

This should be tagged in binary tree/binary search tree

---

@Lakshman Bhaiya wrong tag for this question on GO PDF Draft

---

Thanks, done now👍

Answer 1

answer - (B)

number of distinct BSTs = $\frac{^{2n}C_n}{n+1}$ (or) =$\frac{(2n)!}{(n+1)!n!}$

For a given Binary tree structure, there can be only $1$ BST. Hence, no. of different BSTs with $n$ nodes will be equal to the no. of different binary tree structures possible for $n$ nodes assuming nodes are unlabeled.

For derivation:
http://gatecse.in/number-of-binary-trees-possible-with-n-nodes/

Comments

Distinct  Key  BST and Unlabeled node  BST Both are same and It is equal to Catalan Number?

 

 

@Lakshman Patel RJIT If you have given a particular structure of n nodes(any structure among all possible as in un labeled nodes) there is only one way to fill it to satisfy BST property. Here they are asking BST possible using 4 distinct keys. What you can do is form all possible structure of un labeled nodes(Catalan number) and then in each structure fill the keys using BST property. Hence your statement is true. 

---

It should be 1/n+1 not 1/(n+1!). Please correct it.

---

@Praful932 Answer is correct, please remove flag.

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

Answer 2

Number of binary trees with unlabeled $n-vertices $
$T(n) = T(0)\times T(n-1)+T(1)\times T(n-2)+ \space ... \space+  T(n-1)\times T(0)$

$T(0)=T(1)=1$

$T(4) = T(0)\times T(3) + T(1)\times T(2) + T(2)\times T(1) + T(3)\times T(0)   \rightarrow$ eqn #1

$T(2) = T(0)\times T(1) + T(1)\times T(0) = 2$

$T(3) = T(0)\times T(2) + T(1)\times T(1) + T(2)\times T(0) = 2+1+2 = 5$

Just put values in eqn #1

$T(4)=5+2+2+5=14$

Answer 3

Incase you forgot the formula,

Number of BST's with 2 keys (1,2) = 2

Number of BST's with 3 keys (1,2,3) = 2 + 2 + 1 = (Root is 3) + (Root is 1)  +  (Root is 2)  = 5

Number of BST's with 4 keys (1,2,3,4) = 5 + 5 + 2 + 2 = 14 

Number of BST's with 5 keys (1,2,3,4,5) = 14 + 14 + 5 + 5 + 2 * 2 = 42

Number of BST's with 5 keys (1,2,3,4,5) = Root 5 + Root 1 + Root 4 + Root 2 + Root 3 (2 trees with 2 keys on either side)

 

Answer 4

In general the BST is of the form     

 i.e. 1 node at root, 2 its children, another 4 as its children and so on.

                      

Hence for root=   4C1

for the next two children= 3C2

 and the next= 1C1

also we will add the 2 skew trees

thus total BST=  4C1 * 3C2 * 1C1    +  2 = 14 trees