CODEWITHSUNDEEP
binary-treecombinatorics
ABC
ABC

Reputation: 141

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?

Upvotes: 3

Views: 2025

Answers (2)

Asheesh
Asheesh

Reputation: 11

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

Upvotes: 1

Foo Bah
Foo Bah

Reputation: 26271

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

Upvotes: 0

Related Questions