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

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

(GATE 2005) 

(A) 5 

(B) 14  

(C) 24  

(D) 42 

Answer: (B) 14 

Explanation: 

Here, number of keys, $k = 4$. 

Therefore, the number of distinct binary search trees that can be formed out of 4 distinct keys is 

$= \dfrac{^{2k}C_k}{k + 1}$ 

$ = \dfrac{^{8}C_4}{5}$ 

$= 14$