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
Quiz Practice:
A. 132
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.