GATE CS 2003 Q6 — Binary Search Trees

To find the number of unique binary search trees (BSTs) that can be constructed with $n$ distinct keys, we can choose any element $k$ (where $1 \le k \le n$) as the root of the tree.

Once the $k$-th smallest element is chosen as the root:

• The left subtree must contain the $k-1$ elements that are smaller than the root. The number of ways to form this left subtree is $T(k-1)$.
• The right subtree must contain the remaining $n-k$ elements that are larger than the root. The number of ways to form this right subtree is $T(n-k)$.

Since the structures of the left and right subtrees are independent, the total number of unique BSTs with the $k$-th element as the root is given by the product:

Summing this product over all possible choices of the root $k$ from $1$ to $n$ gives the total number of BSTs $T(n)$:

Comparing this with the given recurrence relation $T(n) = \sum_{k=1}^{n} T(k-1)T(x)$, we get:

Therefore, the correct option is B.