172 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?

| 172 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

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