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)
“Remember? We sat on a slab of rock.
From this distance in time,
it seems the color
of iris, rotting and turning purpler,
but it was only
the usual gray rock”
—Robert Lowell (1917–1977)