<p>An early paper that made this observation explicitly -- that rotations preserve inorder traversals -- is (in Figure 2 of) Sleator and Tarjan's 1983 <a href="http://portal.acm.org/citation.cfm?id=808752&amp;dl=" rel="nofollow">Self-adjusting binary search trees</a>.  The move-to-root heuristic was studied in Allen and Munro's 1978 <a href="http://portal.acm.org/citation.cfm?id=322094&amp;dl=&amp;coll=GUIDE" rel="nofollow">Self-Organizing Binary Search Trees</a> paper.</p>

CC BY-SA 2.5
2010-09-23T14:39:04.207Z
The interesting direction in Per's equivalence is *not* that rotations preserve in-order, but that you can travel in-between any two trees that have the same in-order using rotations.
Radu GRIGore
CC BY-SA 2.5
2010-09-23T14:52:29.140Z
Yes - that's why I included the move-to root.  There's also another paper by Sleator, Tarjan, & Thurston (Rotation Distance, Triangulations, and Hyperbolic Geometry) computing the distances between any two trees, which I didn't include in my answer.  I don't think that Per's observation appears in any one paper as is, but I'd love to be proven wrong.
Lev Reyzin
CC BY-SA 2.5
2010-09-23T14:55:53.357Z
Right, the easy direction is a necessary part of the proofs of correctness for AVL trees, 2-3 trees, etc. The opposite direction is deeper. It says that you don't need any structure-preserving transformations other than tree rotations for completeness.
Per Vognsen
CC BY-SA 2.5
2010-09-23T13:52:15.993Z
2010-09-23T13:52:15.993Z
Lev Reyzin
<p>Since you are interested in the structure of tree rotations, I think you may also be interested in the following paper, which shows that the rotation graph of binary trees of a fixed number of nodes has a Hamiltonian <strong>cycle</strong>. In fact Lucas showed that the cycle can be traversed with constant delay per tree. (A rotation can be performed in $O(1)$ time of course, but it is not obvious a priori that we should be able to decide which rotation to perform along the Hamiltonian cycle in $O(1)$ time.) Naturally, you may also be interested in the references within.</p>

<p>Joan M. Lucas, The rotation graph of binary trees is Hamiltonian, Journal of Algorithms, Volume 8, Issue 4, December 1987, Pages 503-535, ISSN 0196-6774, <a href="http://dx.doi.org/10.1016/0196-6774%2887%2990048-4" rel="nofollow">DOI: 10.1016/0196-6774(87)90048-4</a>.</p>

<p>A simpler proof, also constructive, of the simpler fact that a Hamiltonian <strong>path</strong> exists in the rotation graph can be found in this later paper coauthored by Lucas and her collaborators.</p>

<p>Lucas J. M., Vanbaronaigien D. R., Ruskey F., On Rotations and the Generation of Binary Trees, Journal of Algorithms, Volume 15, Issue 3, November 1993, Pages 343-366, ISSN 0196-6774, <a href="http://dx.doi.org/10.1006/jagm.1993.1045" rel="nofollow">DOI: 10.1006/jagm.1993.1045</a>.</p>

CC BY-SA 2.5
2010-10-28T07:30:22.180Z
2010-10-28T07:30:22.180Z
Maverick Woo
<p>A simpler proof ,also constructive ,of the simpler fact that a Hamiltonian path exits in the rotation graph can be found in this latter .</p>

CC BY-SA 3.0
2013-06-21T13:34:10.180Z
Your answer seems incomplete?
J.y B.y
CC BY-SA 3.0
2013-06-21T13:06:29.487Z
2013-06-21T13:06:29.487Z
007singh
<p>As David Eppstein <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/97#97">points out here</a>, even finding the shortest path for binary trees is not known to be in P. In the comments to that answer he links to the best current bounds</p>

CC BY-SA 2.5
2010-09-26T11:58:28.970Z
I'm accepting this answer since I learned something from it. However, I'd still love to find a reference for the structure theorem if anyone knows one.
Per Vognsen
CC BY-SA 2.5
2010-09-23T14:25:55.247Z
2010-09-23T16:53:35.847Z
2017-04-13T12:32:28.117Z
Suresh Venkat
<p>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:</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>(Bonus brain teaser: What's the best algorithm for finding the shortest sequence of tree rotations that connect two linearly equivalent binary search trees?)</p>

CC BY-SA 2.5
2010-10-29T13:38:53.813Z
Another place to look might be for a reference that equivalence modulo an associative operator is decidable, as this amounts to the same thing. However, all the references that I'm aware of take this fact for granted.
Rob Simmons
<reference-request><ds.data-structures>
Reference for fundamental theorem on tree rotations
Per Vognsen
# Reference for fundamental theorem on tree rotations

(Asked by: username_0 on 2010-09-23)

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?)

**Tags:** reference-request, ds.data-structures

> **Comments:**
> **username_1**: Another place to look might be for a reference that equivalence modulo an associative operator is decidable, as this amounts to the same thing. However, all the references that I'm aware of take this fact for granted.  

---

## 4 answers

### Answer by username_7 on 2010-09-23. Score: 10 | Accepted answer

As David Eppstein [points out here](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/97#97), even finding the shortest path for binary trees is not known to be in P. In the comments to that answer he links to the best current bounds

> **Comments:**
> **username_0**: I'm accepting this answer since I learned something from it. However, I'd still love to find a reference for the structure theorem if anyone knows one.  

---

### Answer by username_2 on 2010-09-23. Score: 11

An early paper that made this observation explicitly -- that rotations preserve inorder traversals -- is (in Figure 2 of) Sleator and Tarjan's 1983 [Self-adjusting binary search trees](http://portal.acm.org/citation.cfm?id=808752&dl=). The move-to-root heuristic was studied in Allen and Munro's 1978 [Self-Organizing Binary Search Trees](http://portal.acm.org/citation.cfm?id=322094&dl=&coll=GUIDE) paper.

> **Comments:**
> **username_3**: The interesting direction in Per's equivalence is *not* that rotations preserve in-order, but that you can travel in-between any two trees that have the same in-order using rotations.  
> **username_2**: Yes - that's why I included the move-to root.  There's also another paper by Sleator, Tarjan, & Thurston (Rotation Distance, Triangulations, and Hyperbolic Geometry) computing the distances between any two trees, which I didn't include in my answer.  I don't think that Per's observation appears in any one paper as is, but I'd love to be proven wrong.  
> **username_0**: Right, the easy direction is a necessary part of the proofs of correctness for AVL trees, 2-3 trees, etc. The opposite direction is deeper. It says that you don't need any structure-preserving transformations other than tree rotations for completeness.  

---

### Answer by username_4 on 2010-10-28. Score: 5

Since you are interested in the structure of tree rotations, I think you may also be interested in the following paper, which shows that the rotation graph of binary trees of a fixed number of nodes has a Hamiltonian **cycle**. In fact Lucas showed that the cycle can be traversed with constant delay per tree. (A rotation can be performed in $O(1)$ time of course, but it is not obvious a priori that we should be able to decide which rotation to perform along the Hamiltonian cycle in $O(1)$ time.) Naturally, you may also be interested in the references within.

Joan M. Lucas, The rotation graph of binary trees is Hamiltonian, Journal of Algorithms, Volume 8, Issue 4, December 1987, Pages 503-535, ISSN 0196-6774, [DOI: 10.1016/0196-6774(87)90048-4](http://dx.doi.org/10.1016/0196-6774%2887%2990048-4).

A simpler proof, also constructive, of the simpler fact that a Hamiltonian **path** exists in the rotation graph can be found in this later paper coauthored by Lucas and her collaborators.

Lucas J. M., Vanbaronaigien D. R., Ruskey F., On Rotations and the Generation of Binary Trees, Journal of Algorithms, Volume 15, Issue 3, November 1993, Pages 343-366, ISSN 0196-6774, [DOI: 10.1006/jagm.1993.1045](http://dx.doi.org/10.1006/jagm.1993.1045).


---

### Answer by username_5 on 2013-06-21. Score: -2

A simpler proof ,also constructive ,of the simpler fact that a Hamiltonian path exits in the rotation graph can be found in this latter .

> **Comments:**
> **username_6**: Your answer seems incomplete?  

---

