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

With $n$ nodes, there are $\frac{^{2n}Cn}{(n+1)}$ distinct tree structures possible.

Corresponding to each structure, only one binary search tree (BST) can be formed because inorder is fixed.

Here, we are already given one such structure therefore only one tree possible.

If binary trees would have been asked, $n!$ trees would have been possible corresponding to each distinct tree structure. Here, tree structure is fixed and hence, we can have only one possibility for BST as elements are distinct. For general cases:
http://gatecse.in/wiki/Number_of_Binary_trees_possible_with_n_nodes 

 

Correct Answer: $B$

Comments

Sir as you say that inorder is given

can you please tell me how.

---

Given n nodes, why answer is 1 BST? There will be 1 BST only if the root is fixed, right?

---

for any given structure no matter how hard u try there will be  only one root of the tree and to satisfy the BST property we will make tree according to it , and it will be unique .

Answer 2

Given binary tree is unlabeled . So as it is given we are not allowed to change the formation of tree. Then To make it BST we can use atmost 1 way . As for particular structure we can not use n! arrangement of nodes (Becasue they are labeled and it is BST not BT)

Comments

@Arjun where they said structure is fixed? They did,'t use the word structure. They have just given the set.

---

In the question they have asked "In how many ways can we populate the tree with the given set ...". Since it is particularly mentioned "populate the tree", hence we have to set values to that structure(given unlabeled binary tree) only and it can be done by 1 way only so, that given unlabeled binary tree turns into a BST.

---

@chandan Ans would be D if it was asked like

How many unique BST are possible using n unlabeled nodes

Answer 3

READ QUESTION VERY CAREFULLY

 

Comments

good approach !

---

thanks!

---

why not you consider skew bst ?

---

Even if it were skewed, only one tree would've been possible. They've said that we are already given an unlabelled binary tree. So it can be skewed or balanced too.. So if we try to form bst, only one would be possible since structure is fixed.

Answer 4

With n nodes there are 2nCn/(n+1) different structure. One structure out of these 2nCn/(n+1) structures is given.

Now no of ways to fill numbers in given structure to ensure BST property is one and only one.

http://gatecse.in/wiki/Number_of_Binary_trees_possible_with_n_distinct_nodes

Comments

In BST left nodes have value less than root and right nodes have value greater than root. SO we could have more than one BST if we take different node for root there will be more than one BST right!!!

---

Take any structure and try to fill that particular structure with these n distinct keys. There will be one and only one sequence possible for a particular structure.