In this paper we will consider tight upper and lower bounds on the weight of the optimal matching for random point sets distributed among the leaves of a tree, as a function of its cardinality. Specifically, given two n sets of points R = {r 1,...,r n } and B = {b 1,...,b n } distributed uniformly and randomly on the m leaves of λ-Hierarchically Separated Trees with branching factor b such that each of its leaves is at depth δ, we will prove that the expected weight of optimal matching between R and B is $\Theta(\sqrt{nb}\sum_{k=1}^h(\sqrt{b}\l)^k)$ , for h = min (δ,log b n). Using a simple embedding algorithm from ℝ d to HSTs, we are able to reproduce the results concerning the expected optimal transportation cost in [0,1] d , except for d = 2. We also show that giving random weights to the points does not affect the expected matching weight by more than a constant factor. Finally, we prove upper bounds on several sets for which showing reasonable matching results would previously have been intractable, e.g., the Cantor set, and various fractals.