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?
@Manish Kumar Tiwari Labeled binary tree implies that the elements are already fixed. You can't change their arrangement. So only 1 possibility.
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$
the word structure is nowhere mentioned in the question. they have used the word 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 likeHow many unique BST are possible using n unlabeled nodes
READ QUESTION VERY CAREFULLY
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
64.3k questions
77.9k answers
244k comments
80.0k users