Number of ways of populating a binary tree to make it a bst

We are given a set of n distinct elements and an unlabeled binary tree with n nodes.In how many can we populate the tree with given set so that it becomes a binary search开发者_开发问答 tree?

when a "tree" would be given for a program(in any language) - it means the root node address will be provided for traversal. Hence according to me since the "Root Node" is provided means the tree structure is already build and fixed into one type.

so i think there can be only one possible way

If by unlabeled you mean there's no specified root node, let G = {G[1]..G[n]} be the set of graphs of the original unlabeled tree rooted at vertices 1 ... n respectively.

Then for each graph G[i] there is exactly one way to populate the tree (why? -- consider what value must be in the root of the tree, and descend recursively).

Once you can show that, the answer must be k, the number of mutually nonisomorphic graphs in the set G