The Gateway to Computer Science Excellence
+2 votes

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


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

in Algorithms by | 182 views

BST are always labeled trees

what is need of binary search tree without labeled keys


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

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.
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.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,315 questions
60,427 answers
95,228 users