Two binary search trees are said to be linearly equivalent when they agree in their in-order traversals. The following theorem explains why tree rotations are so fundamental:
Let A and B be binary search trees. Then A and B are linearly equivalent if and only if they are connected by a sequence of tree rotations.
I noticed this result when I was first learning about data structures long ago and wanted to understand the special status of tree rotations more deeply.
The proof is simple and intuitive: Rotate the least element up to the root position along the leftward spine. By the order invariant, this rearranged tree cannot have a left subtree. Now recurse on the right subtree. The result is a normal form for testing linear equivalence.
While it's a basic theorem, I've never come across it in the literature. I would greatly appreciate a reference for the next time I need to use this result.
(Bonus brain teaser: What's the best algorithm for finding the shortest sequence of tree rotations that connect two linearly equivalent binary search trees?)