What is the number of distinct BSTs possible with 6 distinct keys?

Options

  • A. 132
  • B. 42
  • C. 720
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

A. 132

Detailed Explanation

For six distinct keys, the number of structurally distinct BSTs is the sixth Catalan number. C6 = 132. The Catalan sequence grows rapidly: C3 = 5, C4 = 14, C5 = 42 and C6 = 132. This growth demonstrates that the number of possible tree structures increases much faster than the number of keys. This concept is important in combinatorial DSA problems.