Multiple choice

We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

  1. 0

  2. 1

  3. n!
  4. $\frac{1} {n+1} .^{2n}C_n$
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

The number of distinct BSTs with n distinct keys is the nth Catalan number: C(n) = (1/(n+1)) * (2nCn) = (2n)!/((n+1)!n!). This is a fundamental result in combinatorics - the structure of a BST is determined solely by the relative ordering of elements. With n distinct elements and n nodes, there are exactly C(n) ways to build a BST.

Keep practicing — related questions