Let T(n) be the number of different binary search trees on n distinct…
2003
Let T(n) be the number of different binary search trees on n distinct elements.
Then 
, where x is
- A.
n-k+1
- B.
n-k
- C.
n-k-1
- D.
n-k-2
Attempted by 144 students.
Show answer & explanation
Correct answer: B
Key idea: choose the k-th smallest element as the root. The number of BSTs on n nodes equals the sum over choices of root of (number of left-subtree BSTs) times (number of right-subtree BSTs).
Left subtree size = k-1, so there are T(k-1) possible left subtrees.
Right subtree size = n-k, so there are T(n-k) possible right subtrees.
For a fixed k, the number of BSTs with the k-th element as root is T(k-1)·T(n-k).
Summing over all possible roots k = 1 to n gives the recurrence T(n)=sum_{k=1}^n T(k-1)·T(n-k).
Base cases: T(0)=1 (empty tree) and T(1)=1.
Therefore, in the given expression T(n)=sum_{k=1}^n T(k-1)·T(x), the correct value of x is n-k.