how many distinct binary trees with 4 distinct keys
There are 14 distinct binary trees that can be formed with 4 distinct keys.
Understanding the answer
When the question is “how many distinct binary trees with 4 distinct keys,” in typical data-structures context it refers to the number of distinct binary search trees (BSTs) that can be made using those 4 different keys.
This count is given by the 4th Catalan number.
The general Catalan formula for nnn distinct keys is:
Cn=1n+1(2nn)C_n=\frac{1}{n+1}\binom{2n}{n}Cn=n+11(n2n)
For n=4n=4n=4:
C4=15(84)=15×70=14C_4=\frac{1}{5}\binom{8}{4}=\frac{1}{5}\times 70=14C4=51(48)=51×70=14
So:
- Number of distinct binary trees with 4 nodes (distinct keys) = 14.
Intuitively, each different “shape” of a 4-node binary tree corresponds to one of these 14 possibilities, and these are exactly the structures you can realize as BSTs with 4 distinct keys.
TL;DR: For the query “how many distinct binary trees with 4 distinct keys” the correct answer used in exams and tutorials is 14 , coming from the 4th Catalan number.
Information gathered from public forums or data available on the internet and portrayed here.
