The rotation distance between any two binary trees with the same number of nodes is the minimum number of rotations needed to transform one into the other. With this distance, the set of n-node binary trees becomes a metric space: the distance is symmetric, positive when given two different trees, and satisfies the triangle inequality.
It is an open problem whether there exists a polynomial time algorithm for calculating rotation distance.
Daniel Sleator, Robert Tarjan and William Thurston showed that the rotation distance between any two n-node trees (for n ≥ 11) is at most 2n − 6, and that infinitely many pairs of trees are this far apart.
Read more about this topic: Tree Rotation
Famous quotes containing the words rotation and/or distance:
“The lazy manage to keep up with the earth’s rotation just as well as the industrious.”
—Mason Cooley (b. 1927)
“Small, black, as flies hanging in heat, the Boys,
Until the distance throws them forth, their hum
Bulges to thunder held by calf and thigh.”
—Thom Gunn (b. 1929)