1.6k views

How many distinct binary search trees can be created out of $4$ distinct keys?

1. $5$
2. $14$
3. $24$
4. $42$
edited | 1.6k views

number of distinct BSTs = $\frac{^{2n}C_n}{n+1}$ (or) =$\frac{(2n)!}{(n+1)!n!}$

For a given Binary tree structure, there can be only $1$ BST. Hence, no. of different BSTs with $n$ nodes will be equal to the no. of different binary tree structures possible for $n$ nodes.

edited by
+2
Yes it will be equal to Catalan no.
+6
0
sir distinct keys does not mean labelled nodes?
+1

no because distinct keys in BST must satisfy a property. while in a labelled nodes binary tree there is  no such restriction

0
@Arjun sir

Distinct  Key  BST and Unlabeled node  BST Both are same and It is equal to Catalan Number?
0

Lakshman Patel RJIT  yes try creating distinct binary trees with 3 unlabeled nodes and also try creating BST's with keys {1,2,3} and it is unlabeled Binary tree not unlabeled BST

0

@Mk Utkarsh I'm little bit confuse

can you explain?

0
$\text{No. of BST with n nodes}$=$\sum_{i=1}^{n} T(i-1)*T(n-i)$ $\text{where}$ $T(0)=T(1)=1$

Number of binary trees with n-vertices =2n!/n!(n+1)! =14 so option B is answer

Incase you forgot the formula,

Number of BST's with 2 keys (1,2) = 2

Number of BST's with 3 keys (1,2,3) = 2 + 2 + 1 = (Root is 3) + (Root is 1)  +  (Root is 2)  = 5

Number of BST's with 4 keys (1,2,3,4) = 5 + 5 + 2 + 2 = 14

Number of BST's with 5 keys (1,2,3,4,5) = 14 + 14 + 5 + 5 + 2 * 2 = 42

Number of BST's with 5 keys (1,2,3,4,5) = Root 5 + Root 1 + Root 4 + Root 2 + Root 3 (2 trees with 2 keys on either side)