1.3k views

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

1. 5
2. 14
3. 24
4. 42
recategorized | 1.3k 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
Yes it will be equal to Catalan no.
sir distinct keys does not mean labelled nodes?

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

@Arjun sir

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

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

@Mk Utkarsh I'm little bit confuse

can you explain?

+1 vote

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