How many distinct binary search trees can be created out of 4 distinct keys?
2005
How many distinct binary search trees can be created out of 4 distinct keys?
- A.
5
- B.
14
- C.
24
- D.
42
Attempted by 434 students.
Show answer & explanation
Correct answer: B
Key idea: The number of distinct binary search tree shapes with n distinct keys is the nth Catalan number.
Use the Catalan formula:
Cn = (1/(n+1)) * binomial(2n, n).
Compute for n = 4:
binomial(8,4) = 70, so C4 = (1/5) * 70 = 14.
Alternatively, use the recurrence: C4 = C0*C3 + C1*C2 + C2*C1 + C3*C0 = 1*5 + 1*2 + 2*1 + 5*1 = 14.
Answer: 14