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

- Dec 21st 2011, 07:40 PMnikhilbhrGraph 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?

- Dec 22nd 2011, 04:04 AMemakarovRe: Graph Theory:Tree
I assume the elements that are to become labels are linearly ordered. Have you tried small examples of trees?

- Dec 22nd 2011, 04:20 AMnikhilbhrRe: Graph Theory:Tree
Theres no ordering among the element , then known information is that the elements are distinct.

- Dec 22nd 2011, 04:22 AMemakarovRe: Graph Theory:Tree
The definition of the binary search tree assumes that node labels are ordered.

- Dec 22nd 2011, 04:26 AMnikhilbhrRe: 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.. - Dec 22nd 2011, 04:30 AMnikhilbhrRe: Graph Theory:Tree
Ans to this question is (1/(n+1)) *(2n chooses n)

- Dec 22nd 2011, 08:46 AMemakarovRe: Graph Theory:Tree
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). - Dec 22nd 2011, 05:23 PMnikhilbhrRe: 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