How many distinct binary search trees can be created using 3 distinct keys?

Options

  • A. 3
  • B. 5
  • C. 6
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

B. 5

Detailed Explanation

For N distinct keys, the number of structurally different BSTs is the N-th Catalan number. For N = 3, C3 = 5. Therefore, three distinct keys can form 5 distinct BSTs. The beginning of the Catalan sequence is 1, 1, 2, 5, 14, 42. These values frequently appear in DSA questions involving binary trees, BSTs, recursion, parenthesization, and other combinatorial structures.