  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 32 n$. Two recent results of Aichholzer et al. and
Bousquet et al. improved the Avis and Fukuda upper bound by proving that there
always exists a flip sequence of length respectively at most $2n - \log n$ and
$2n - \sqrt{n}$. We improve the upper bound by a linear factor for the first
time in 25 years by proving that there always exists a flip sequence between
any pair of non-crossing spanning trees $T_1,T_2$ of length at most $c n$ 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 53 |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 rotations.
