how many distinct binary search trees can be created out of 4 distinct keys
14 distinct binary search trees can be created with 4 distinct keys.
This classic problem in data structures hinges on the Catalan numbers, which count valid BST structures for n unique keys regardless of their specific values (assuming sorted order like 1,2,3,4). The nth Catalan number formula is Cn=1n+1(2nn)C_n=\frac{1}{n+1}\binom{2n}{n}Cn=n+11(n2n), and for n=4, it yields exactly 14.
Catalan Numbers Breakdown
Catalan numbers CnC_nCn give the count of BSTs:
- C0=1C_0=1C0=1, C1=1C_1=1C1=1
- C2=2C_2=2C2=2
- C3=5C_3=5C3=5
- C4=14C_4=14C4=14
n (keys)| BST Count| Formula Value
---|---|---
1| 1| C1=1C_1=1C1=1 3
2| 2| C2=2C_2=2C2=2 3
3| 5| C3=5C_3=5C3=5 3
4| 14| C4=14C_4=14C4=14 39
5| 42| C5=42C_5=42C5=42 3
Why 14 for n=4?
Imagine keys A<B<C<D. Each tree picks a root, splitting left/right subtrees recursively:
- Root A: 1 way for right subtree (BSTs of {B,C,D} = C_3=5), left empty → 5 trees
- Root B: left {A}=1 way, right {C,D}=2 ways → 1*2=2 trees
- Root C: left {A,B}=2, right {D}=1 → 2*1=2 trees
- Root D: left {A,B,C}=5, right empty → 5 trees
Total: 5+2+2+5=14. This recursive logic f(n)=∑i=1nf(i−1)⋅f(n−i)f(n)=\sum_{i=1}^nf(i-1)\cdot f(n-i)f(n)=∑i=1nf(i−1)⋅f(n−i) (with f(0)=1) matches the Catalan pattern.
Common Confusions
- Not 24 : That's 4! permutations, but many form identical BST shapes after insertion.
- Not 8 : Too low; misses balanced/skewed variants.
- Binary trees (no search property) total more: ~336 for labeled nodes, but BSTs enforce order.
This pops up in exams like GATE/BPSC (e.g., options 8/14/24), interview puzzles, and algorithm design—still trending in 2026 CS prep forums.
TL;DR: 14 BSTs for 4 keys.
Information gathered from public forums or data available on the internet and portrayed here.
