How many Binary Search Trees are possible for a labelled nodes?

Question

Let us there are n nodes which are labelled.

Then the number of trees possible is given by the Catalan Number i.e $\binom{2n}{n} / (n+1)$

Then the binary search trees possible is just $1$?

Comments

For a given unlabeled tree, there is only 1 way a BST can be formed.

For n labeled nodes, Catalan Number of BST can be formed.

---

Hi the language of the question is pretty vague, please copy and paste the exact question.

Answer 1

For example, if number of nodes are 3 then 5 unlabelled binary trees[2nCn/(n+1)] are possible with 3 nodes. So, for each unlabelled binary tree there are 6 possible labelled binary trees[(i.e.,n!,(3!=3*2*1)] . Suppose that 3 labelled nodes are 1,2,3 and inorder traversal for this labelled binary tree is 123, then among those 6 possible binary trees you can get only one binary search tree as inorder 123.

Answer 2

For a given unlabeled tree(ie structure of Binary tree is not fixed) we can have [2nCn/(n+1)] structures,

For no of nodes= 3

no of structure= 5

now for each binary tree structure  we can arrange n values in n! ways..but all will not be binary search tree.

To make them a binary search tree there is only one fix order of n values. That's why for each structure we have n! binary tree but only 1 Binary search tree..

So for n= 3 (in case of unlabeled)

Total binary tree possible= 5*3! = 30

Total binary search tree possible= 5*1= 5

Answer 3

catalan number. for N labelled nodes, the nos of Binary Search Trees is catalan number.

Answer 4

According to given in CLRS the total number of Binary Search tree is itself the catalan number

(2n C n) /(n+1)