In the 1988 paper Rotation Distance, Triangulations, and Hyperbolic Geometry, Sleator, Tarjan and Thurston show that for any pair of $n$-node binary trees, the maximum rotation distance between them is $2n-6$ for all $n \ge 11$.

They also claim that this bound is tight for sufficiently large $n$. I see how they achieved the upper bound of $2n-6$ rotations but I am now trying to understand their proof of the lower bound. To the best of my understanding, their argument relies on triangulating a polyhedron and looking at volumes in hyperbolic space.

I'm having trouble connecting these fairly technical mathematical claims back to actual binary trees. In particular, what would be a concrete example of two binary trees (or families of binary trees) which meet this lower bound and actually require $2n-6$ rotations to transform one tree into the other?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.