How many different binary search trees can be constructed with 6 different…
2021
How many different binary search trees can be constructed with 6 different nodes?
Answer: D. 132 — The number of distinct binary search trees that can be formed with n distinct nodes is given by the nth Catalan number. The formula for the nth Catalan number…
- A.
64
- B.
128
- C.
32
- D.
132
Attempted by 683 students.
Show answer & explanation
Correct answer: D
The number of distinct binary search trees that can be formed with n distinct nodes is given by the nth Catalan number.
The formula for the nth Catalan number is:
For n = 6:
Calculating:
12! = 479001600
7! = 5040
6! = 720
C_6 = 479001600 / (5040 * 720) = 479001600 / 3628800 = 132
Therefore, the number of distinct binary search trees with 6 nodes is 132.
Loading lesson…