The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

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 Loyal (6.7k points) | 133 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.
by Active (4.9k points)

Related questions

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
49,896 questions
55,153 answers
85,319 users