Let T(n) be the number of different binary search trees on n distinct elements. Then T(n) = sum_{k=1}^{n} T(k-1) * T(n-k...

Question

Let T(n) be the number of different binary search trees on n distinct elements. Then T(n) = sum_{k=1}^{n} T(k-1) * T(n-k), where T(0) = 1. Which of the following is T(n)?
A. n = 4k + 1
B. n = k
C. n = k - 1
D. n = k - 2

Accepted Answer

T(n) is the n-th Catalan number = C(2n, n)/(n+1). The summation runs from k=1 to n, so the answer is option B (n = k, meaning the upper bound equals n). T(n) counts how many structurally different Binary Search Trees can be built with n distinct elements. The recurrence T(n) = sum_{k=1}^{n} T(k-1)*T(n-k) with T(0)=1 is the well-known Catalan number recurrence. For each choice of root k (the k-th smallest element), there are T(k-1) ways to arrange the left subtree and T(n-k) ways to arrange the right subtree. The question asks which formula T(n) satisfies or what the index relation is.

Let T(n) be the number of different binary search trees on n distinct elements. Then T(n) = sum_{k=1}^{n} T(k-1) * T(n-k), where T(0) = 1. Which of the following is T(n)? A. n = 4k + 1 B. n = k C. n = k - 1 D. n = k - 2