How many distinct binary search trees can be created out of 4 distinct keys?
2011
How many distinct binary search trees can be created out of 4 distinct keys?
- A.
5
- B.
14
- C.
24
- D.
35
Attempted by 326 students.
Show answer & explanation
Correct answer: B
The number of distinct binary search trees that can be formed with n unique keys is given by the nth Catalan number. The formula for the nth Catalan number is C_n = (1 / (n + 1)) * binomial(2n, n). For n = 4 keys, we calculate C_4 = (1 / 5) * binomial(8, 4). The binomial coefficient binomial(8, 4) equals (8 * 7 * 6 * 5) / (4 * 3 * 2 * 1) = 70. Therefore, C_4 = 70 / 5 = 14.
A video solution is available for this question — log in and enroll to watch it.