Algorithms for tree rotation
It's fixed-parameter tractable in the natural parameter, the distance. So if two trees have distance $k$ you can find the distance in time polynomial + $f(k)$ for some function $f$. The proof is a kernelization that produces a kernel of size $O(k)$ so putting that together with the naive method of finding a shortest path in the flip graph gives time singly exponential in $k$. See "Rotation distance is fixed-parameter tractable", Cleary &amp; St. John, Inf. Proc. Lett. 2009, and "An improved kernel size for rotation distance in binary trees", Lucas, Inf. Proc. Lett. 2010. See also "A linear-time approximation for rotation distance", Cleary &amp; St. John, JGAA 2010.