Is there any known result on approximating an arbitrary tree metric by an HST metric (or an Ultrametric)? What is the distortion? Thanks.
The distortion of embedding any $n$-point metric in ultrametric is at most $n-1$, and on the other hand, the distortion of embedding the path metric $P_n$ in ultrametric is at least $n-1$.
Similarly, if you are interested in probabilistic embedding, then by Fakcharoenphol, Rao, and Talwar result mentioned above, any $n$-point metric space probabilistically embeds in ultrametric with distortion $O(\log n)$. On the other hand, the distortion of probabilistically embedding $P_n$ in ultrametric is $\Omega(\log n)$.
There is a classic result by Fakcharoenphol, Rao, and Talwar showing that any $n$ point metric space can be embedded into an HST metric with expected distortion $O(log\, n)$.
One should keep in mind that this result holds only for probabilistic embeddings, since there are metrics (such as the $n$-cycle) which will give you an $\Omega(n)$ distortion if you only accept deterministic embeddings.