Optimal transport ($\OT$) theory provides a useful set of tools to compare probability distributions. As a consequence, the field of $\OT$ is gaining traction and interest within the machine learning community. A few deficiencies usually associated with $\OT$ include its high computational complexity when comparing discrete measures, which is quadratic when approximating it through entropic regularization; or supercubic when solving it exactly. For some applications, the fact that $\OT$ distances are not usually negative definite also means that they cannot be used with usual Hilbertian tools. In this work, we consider a particular family of ground metrics, namely tree metrics, which yield negative definite $\OT$ metrics that can be computed in linear time. By averaging over randomly sampled tree metrics, we obtain a tree-sliced-Wasserstein distance. We illustrate that the proposed tree-sliced-Wasserstein distances compare favorably with other baselines on various benchmark datasets.