How many distinct BSTs can be constructed with 3 distinct keys?
2008
How many distinct BSTs can be constructed with 3 distinct keys?
- A.
4
- B.
5
- C.
6
- D.
9
Attempted by 526 students.
Show answer & explanation
Correct answer: B
Answer: 5
Explanation: Count the distinct binary search tree shapes for 3 distinct keys by considering each possible root and multiplying the number of left and right subtree shapes.
If the smallest key is the root: left subtree has 0 nodes (1 shape) and right subtree has 2 nodes (2 shapes) => 1 × 2 = 2.
If the middle key is the root: left subtree has 1 node (1 shape) and right subtree has 1 node (1 shape) => 1 × 1 = 1.
If the largest key is the root: left subtree has 2 nodes (2 shapes) and right subtree has 0 nodes (1 shape) => 2 × 1 = 2.
Total distinct BSTs = 2 + 1 + 2 = 5.
Alternative view: This is the third Catalan number. Catalan formula: Cn = (2n choose n)/(n+1). For n = 3, C3 = (6 choose 3)/4 = 20/4 = 5.