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?
Printable View
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?
I assume the elements that are to become labels are linearly ordered. Have you tried small examples of trees?
Theres no ordering among the element , then known information is that the elements are distinct.
The definition of the binary search tree assumes that node labels are ordered.
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..
Ans to this question is (1/(n+1)) *(2n chooses n)
How exactly do you take the current elements into account to find an appropriate place for the new element?Quote:
Originally Posted by nikhilbhr
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).
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