  We derive tight bounds on the expected weights of several combinatorial
optimization problems for random point sets of size $n$ distributed among the
leaves of a balanced hierarchically separated tree. We consider {\it
monochromatic} and {\it bichromatic} versions of the minimum matching, minimum
spanning tree, and traveling salesman problems. We also present tight
concentration results for the monochromatic problems.
