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

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