In this paper, we defined a novel edit distance for merge trees, which we argued to be suitable for a broad range of applications. Relying also on some technical results contained in other works, we investigated its stability properties, which ended up being analogous to the ones of the 1-Wasserstein distance between persistence diagrams. We tested and compared our metric against the interleaving distance in several simulations and case studies, highlighting the trade-off between stability and sensitivity when choosing the appropriate metric for a given data analysis problem, much alike the bias-variance trade-off in statistical modeling. In the appendix, we also compared our metric with other edit distances appearing in the literature, with both theoretic and practical considerations.

In this work, we studied the interleaving distance between merge trees from a combinatorial point of view. In the first part of the paper, we used a particular type of matching between trees to obtain a novel formulation of the distance. This formulation unveiled a link connecting the interleaving distance and edit distances between merge trees, which was of great interest due to the recursive decomposition properties and constrained formulations with polynomial time algorithms that these distances often enjoyed. In the second part of the paper, we built on this connection by applying tools from edit distances to obtain a constrained formulation of the interleaving distance and a recursive procedure which allowed us to find algorithms for upper and lower bounds of the interleaving distance. We implemented those algorithms and used them to test another upper bound presented by other authors, and tackled some simulations and case studies. Motivated by the literature on edit distances, we believe that our novel formulation could lead to novel heuristics to compute the interleaving distance and that applying our recursive scheme to the constrained interleaving distance would produce polynomial time upper bounds of practical relevance.