I assume the elements that are to become labels are linearly ordered. Have you tried small examples of trees?
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).