How many distinct binary search trees can be created out of 4 distinct keys?
2024
How many distinct binary search trees can be created out of 4 distinct keys?
- A.
8
- B.
24
- C.
14
- D.
More than one of the above
- E.
None of the above
Attempted by 415 students.
Show answer & explanation
Correct answer: C
The number of distinct binary search trees (BSTs) that can be formed with n distinct keys is given by the nth Catalan number.
The formula for the nth Catalan number is:
For n = 4:
Calculating:
8! = 40320, 5! = 120, 4! = 24
C_4 = 40320 / (120 × 24) = 40320 / 2880 = 14
Thus, 14 distinct binary search trees can be formed with 4 distinct keys.
हिन्दी उत्तर:
n भिन्न कुंजियों के साथ बनाए जा सकने वाले विभिन्न बाइनरी सर्च ट्री (BST) की संख्या n वां कैटलान संख्या द्वारा दी जाती है।
n वें कैटलान संख्या का सूत्र है:
n = 4 के लिए:
गणना करने पर:
8! = 40320, 5! = 120, 4! = 24
C_4 = 40320 / (120 × 24) = 40320 / 2880 = 14
इसलिए, 4 भिन्न कुंजियों के साथ 14 विभिन्न बाइनरी सर्च ट्री बनाए जा सकते हैं।