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

- December 21st 2011, 06: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?

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

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

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

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

- December 22nd 2011, 07: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). - December 22nd 2011, 04: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