recategorized by
31,479 views
48 votes
48 votes

We are given a set of $n$ distinct elements and an unlabeled binary tree with $n$ nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

  1. $0$
  2. $1$
  3. $n!$
  4. $\frac{1} {n+1} .^{2n}C_n$
recategorized by

9 Answers

6 votes
6 votes
Just the simple logic is that we have 2nCn/(n+1) unlabelled trees , now each unlabelled tree will always correspond to one BST , consider 1,2,3 now say you draw a right skewed unlabelled tree , now u can label it only in one way 1 2 3 to form a BST , if say u draw a left skewed unlabelled tree , then u can label it as 3 2 1 , to form BST therefore each unlabelled tree gives rise to only 1 BST.

 

But in the question it is already given that we are provided with one unlabelled tree therefore there is only 1 way in which we can populate it to form a BST therefore answer is option A .
5 votes
5 votes
Take any structure formed by n unlabeled binary tree ... suppose n=3 ... then try to label it which will be n! (here 3!) ... then U will find only one structure satisfying the conditions of BST .. So B is the answer ...
0 votes
0 votes

i found all the unlabeled trees can be binary search trees. Please check this and correct if iam wrong.Guys, please check whether it is correct or not.

Answer:

Related questions

18 votes
18 votes
2 answers
2
25 votes
25 votes
2 answers
3