Number of binary search trees

Question

How many different binary search trees can be constructed using six distinct keys?

1.   256
2.   128
3.   132
4.   264

Comments

The first few Catalan numbers for n=1, 2, ... are 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 

---

or we can use formula 2nCn/(n+1)

12C6/7   12*11=132

---

good read: https://gatecse.in/number-of-binary-trees-possible-with-n-nodes/

Answer 1

We use the catalan number Cn = (2n)!/ (n+1)!*n! to find the number of binary search tree with n vertices.

So in this case n = 6,

Hence 12!/7!*6! = 132

Comments

It is same as binary trees with unlabelled nodes.

---

@Sukannya

# of BST with 'n' distinct nodes = # of unlabeled binary trees with 'n' nodes  = $\frac{\binom{2n}{n}}{n+1}$

---

Ya, @joshi_nitish. It was a typo and my stupid habit of writing wrong ans inspite of knowing the correct ones... :)

Answer 2

132 BST trees are possible

Answer 3

Get the no. of bst's possible with 'n' nodes

                                          2nCn/n+1 (Catalyn no.)

Answer 4

12C6/6+1

12!/6!*6!*7

=>132

Ans is 132