How many distinct Binary Search Trees can be formed using 3 distinct keys?
Options
- A. 3
- B. 5
- C. 6
- D. More than one of the above
- E. None of the above
Quiz Practice:
B. 5
The number of structurally distinct BSTs that can be formed using N distinct keys is given by the Catalan number CN. For N = 3, C3 = 5. Therefore, three distinct keys can form five different BST structures. The Catalan sequence begins 1, 1, 2, 5, 14, 42 and is frequently used in questions involving binary search trees, binary tree structures, and other recursive combinatorial problems.