Gromov-Wasserstein (GW) is a powerful tool to compare probability measures whose supports are in different metric spaces. However, GW suffers from a computational drawback since it requires to solve a complex non-convex quadratic program. In this work, we consider a specific family of cost metrics, namely, tree metrics for supports of each probability measure, to develop efficient and scalable discrepancies between the probability measures. Leveraging a tree structure, we propose to align \textit{flows} from a root to each support instead of pair-wise tree metrics of supports, i.e., flows from a support to another support, in GW. Consequently, we propose a novel discrepancy, named \emph{Flow-based Alignment} (\FlowAlign), by matching the flows of the probability measures. \FlowAlign~is computationally fast and scalable for large-scale applications. Further exploring the tree structure, we propose a variant of \FlowAlign, named \emph{Depth-based Alignment} (\DepthAlign), by aligning the flows hierarchically along each depth level of the tree structures. Theoretically, we prove that both \FlowAlign~and \DepthAlign~are pseudo-metrics. We also derive tree-sliced variants of the proposed discrepancies for applications without priori knowledge about tree structures for probability measures, computed by averaging \FlowAlign/\DepthAlign~using random tree metrics, adaptively sampled from supports of probability measures. Empirically, we test our proposed approaches against other variants of GW baselines on a few benchmark tasks.