A non-crossing spanning tree of a set of points in the plane is a spanning tree whose edges pairwise do not cross. Avis and Fukuda in 1996 proved that there always exists a flip sequence of length at most \(2n-4\) between any pair of non-crossing spanning trees (where n denotes the number of points). Hernando et al. proved that the length of a minimal flip sequence can be of length at least \(\frac{3}{2} n\) . Two recent results of Aichholzer et al. and Bousquet et al. improved the upper bound by Avis and Fukuda by proving that there always exists a flip sequence of length respectively at most \(2n - \log n\) and \(2n - \sqrt{n}\) when the points are in convex position. We pursue the investigation of the convex case by improving the upper bound by a linear factor for the first time in 30 years. We prove that there always exists a flip sequence between any pair of non-crossing spanning trees \(T_1,T_2\) of length at most cn where \(c \approx 1.95\) . Our result is actually stronger since we prove that, for any two trees \(T_1,T_2\) , there exists a flip sequence from \(T_1\) to \(T_2\) of length at most \(c |T_1 \setminus T_2|\) . We also improve the best lower bound in terms of the symmetric difference by proving that there exists a pair of trees \(T_1,T_2\) such that a minimal flip sequence has length \(\frac{5}{3} |T_1 \setminus T_2|\) , improving the lower bound of Hernando et al. by considering the symmetric difference instead of the number of vertices. We generalize this lower bound construction to non-crossing flips (where we close the gap between upper and lower bounds) and edge-rotations.
