+1 vote
133 views

I have doubt when its asked to know number of labelled and unlabelled binary tree :

For labelled = (On basis of labelling)

 T(n) = 2nCn/(n+1) * n!

For unlabelled = (On Basis of Geometric Sturucture)

T(n) = (2n)Cn/n+1

Right?

What if its Asked for BST what will be the answer in both the above cases and Why?

| 133 views
+4

BST are always labeled trees

what is need of binary search tree without labeled keys

+1

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

It will always be labeled as said above and will be equal to Catalan number, for why read above post.

+1
Labeled BST = $\frac{C(2n, n)}{n+1}$ Which is Catalan Number.

Unlabeled BST = No such BST are possible.

Labeled BT = $\frac{C(2n, n)}{n+1}*n!$

Unlabeled BT = $\frac{C(2n, n)}{n+1}$.

Note that Unlabeled BT is nothing but arranging nodes in the binary tree format.
0
Thanks it cleared my doubt

## 1 Answer

0 votes
since, u have metioned that u need no of binary search tree definitely u must have unique searching sequence , so there will be only one bst for given sequence , and also keep in mind bst is always drawn for values which is comparable among each other thats why we have only one bst for given sequence.
by Active (4.9k points)

0 votes
1 answer
1
0 votes
1 answer
2
0 votes
0 answers
3
0 votes
2 answers
4
0 votes
1 answer
5
+8 votes
1 answer
6
0 votes
1 answer
7