what about this?This is the same structure and can be populated in two different ways.

for 15 nodes BST can be populated in 8 ways.

The Gateway to Computer Science Excellence

+29 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?

- $0$
- $1$
- $n!$
- $\frac{1} {n+1} .^{2n}C_n$

–5

what about this?This is the same structure and can be populated in two different ways.

for 15 nodes BST can be populated in 8 ways.

+1

in 2nd pic.- Every element of right subtree should be greater than 5 but here 4 is present so it is wrong.

0

he said an unlabeled binary means out of all possible unlabel binary tree we took on of them then they ask how many way u form bst. so only one way

0

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

+54 votes

Best answer

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$

+1

word set is given means it contains some value so there is only 1 way to put the value into the node(means populate the tree with the given set) as already structure is fixed for BST.

+29 votes

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)

+13

Yes. Here tree structure is fixed and hence we can have only 1 possibility for BST as elements are distinct. For general cases:

http://gatecse.in/wiki/Number_of_Binary_trees_possible_with_n_nodes

http://gatecse.in/wiki/Number_of_Binary_trees_possible_with_n_nodes

0

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

+1

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.

+9 votes

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

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

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

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

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

0

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

–3 votes

0

Structure is fixed here. So, we can have only 1 way of filling as elements are distinct.

http://gatecse.in/wiki/Number_of_Binary_trees_possible_with_n_distinct_nodes

52,375 questions

60,583 answers

202,002 comments

95,403 users