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

Thanks, done now👍

---

Catalan number 🙏

---

$\text{ Option B) 14  is the answer.}$
Catalan number = $\frac{^{2n}C_n}{n+1}$  or  $\frac{(2 * n)!}{(n+1)! * n!}$

$\frac{(2 * 4 )!}{(4+1)! * 4!}$ = $\frac{8 !}{5!  *  4!}$ = $\frac{8 * 7 * 6 }{ 4 * 6}$ = $14$

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

Answer 5

The number of distinct binary search trees that can be created out of 4 distinct keys is 14 (Option B).

---

Explanation

The number of distinct Binary Search Trees (BSTs) that can be formed using $n$ distinct keys is equal to the number of structurally unique binary trees with $n$ nodes. This value is determined by the $n^{th}$ Catalan number, denoted as $C_n$.

1. The Logic Behind the Calculation

For any unlabeled binary tree structure with $n$ nodes, there is exactly one way to fill it with $n$ distinct keys to satisfy the BST property (because the keys must appear in sorted order during an Inorder traversal). Therefore:

Number of distinct BSTs with $n$ keys = Number of unique binary tree structures with $n$ nodes.

2. The Catalan Formula

The formula for the $n^{th}$ Catalan number is:

 

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

3. Step-by-Step Calculation for $n=4$

To find the answer for 4 distinct keys:

• Step 1: Calculate the Binomial Coefficient

   

  $$\binom{2n}{n} = \binom{8}{4} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70$$

• Step 2: Apply the divisor $(n+1)$

   

  $$C_4 = \frac{70}{4+1} = \frac{70}{5} = 14$$

 

Answer 6

can be done by 2 techniques :

1) by formulae : 1 / (n + 1) * (2n c n)

2) by recurence : t(n) = summition k =1 to n t(k-1) * t(n-k).