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$
GATE previous year solutions for CS and IT