GATE CSE 2011 | Question: 29

Question

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?

• A. $0$
• B. $1$
• C. $n!$
• D. $\frac{1} {n+1} .^{2n}C_n$

Comments

if it is given a labeled binary tree with n nodes then???

---

@Manish Kumar Tiwari Labeled binary tree implies that the elements are already fixed. You can't change their arrangement. So only 1 possibility.

---

Video solution 

Answer 1

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 .

Comments

In the question, the tree is also given.

---

Thankss sir for correction I have edited my answer .

---

That unlabelled tree rises one BST. So answer 1. I m correct ?

Answer 2

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

Answer 3

i found all the unlabeled trees can be binary search trees. Please check this and correct if iam wrong.

Comments

@Sangeeth680 But here we are provided with one such unlabeled binary tree. So here we have the structure of the tree and we have to fill it, in order to make it a BST which can be done in only 1 way.

Answer 4

 

Option D is the Answer