1. ## Graph Theory:Tree

Given a set of n distinct elements and an unlabeled binary tree of n nodes. In how many ways we can populate the tree with the given set so that it becomes a binary search tree?

2. ## Re: Graph Theory:Tree

I assume the elements that are to become labels are linearly ordered. Have you tried small examples of trees?

3. ## Re: Graph Theory:Tree

Theres no ordering among the element , then known information is that the elements are distinct.

4. ## Re: Graph Theory:Tree

The definition of the binary search tree assumes that node labels are ordered.

5. ## Re: Graph Theory:Tree

You just peek any element from the set ,make it root node
then peek next element and place it at appropriate place based on current elements in the treee and so on..

6. ## Re: Graph Theory:Tree

Ans to this question is (1/(n+1)) *(2n chooses n)

7. ## Re: Graph Theory:Tree

Originally Posted by nikhilbhr
You just peek any element from the set ,make it root node
then peek next element and place it at appropriate place based on current elements in the treee and so on..
How exactly do you take the current elements into account to find an appropriate place for the new element?

The problem statement does not make much sense to me. If a tree is given, then each labeling, viewed as a binary search tree, corresponds to one and only one ordering of the labels (i.e., elements).

8. ## Re: Graph Theory:Tree

Actually this question is from IIT GATE examination.I was not able to solve this question.I have written the question as it was in the examination