Chain rotations: A new look at tree distance

As well known the rotation distance $D(S,T)$ between two binary trees S, T of n vertices is the minimum number of rotations of pairs of vertices to transform S into T. We introduce the new operation of chain rotation on a tree, involving two chains of vertices, that requires changing exactly three pointers in the data structure as for a standard rotation, and define the corresponding chain distance $C(S,T)$ . As for $D(S,T)$ , no polynomial time algorithm to compute $C(S,T)$ is known. We prove a constructive upper bound and an analytical lower bound on $C(S,T)$ based on the number of maximal chains in the two trees. More precisely we prove the general upper bound $C(S,T)⩽n‐1$ and we show that there are pairs of trees for which this bound is tight. No similar result is known for $D(S,T)$ where the best upper and lower bounds are $2n‐6$ and $\frac{5}{3}n‐4$ respectively.