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

Best answer
87 votes
87 votes

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$

edited by
32 votes
32 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)
21 votes
21 votes

READ QUESTION VERY CAREFULLY

 

10 votes
10 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

Answer:

Related questions

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