On Rotation Distance of Rank Bounded Trees

Anoop S. K. M.; Jayalal Sarma

arxiv: 2304.03985 · v3 · submitted 2023-04-08 · 💻 cs.DS

On Rotation Distance of Rank Bounded Trees

Anoop S. K. M. , Jayalal Sarma This is my paper

Pith reviewed 2026-05-24 09:12 UTC · model grok-4.3

classification 💻 cs.DS

keywords rotation distancebinary treesrank bounded treesskew treestree rotationsalgorithmic combinatoricspermutation representations

0 comments

The pith

The rotation distance problem on binary trees reduces in polynomial time to its rank-bounded version.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors prove that the long-standing problem of computing the minimum rotations to transform one binary tree into another reduces in polynomial time to the restricted version in which every intermediate tree must have rank at most a given bound r. For the special case of rank-1 trees, which are exactly the skew trees, they give an explicit O(n squared) algorithm that computes the exact distance and show that this distance is always at most n squared. They also prove a general upper bound on the rank-bounded distance that is quadratic in n and linear in the sum of the input ranks. The proofs proceed by mapping trees to permutations and bivariate polynomials and deriving structural characterizations that hold for skew trees.

Core claim

The rotation distance problem reduces in polynomial time to the rank bounded rotation distance problem. For any two skew trees an O(n squared) algorithm computes d1(T1,T2) and the unrestricted distance satisfies d(T1,T2) less than or equal to n squared. For trees of ranks at most r1 and r2 the quantity dr(T1,T2) is at most n squared times (1 plus (2n plus 1) times (r1 plus r2 minus 2)).

What carries the argument

The rank-bounded rotation distance dr(T1,T2), the length of the shortest rotation sequence transforming T1 into T2 while keeping every intermediate tree of rank at most r.

If this is right

Any algorithm that solves the rank-bounded problem yields a corresponding algorithm for the general problem via the reduction.
The distance between any two skew trees is at most n squared and can be computed in quadratic time.
The stated upper bound on dr(T1,T2) holds for every pair of trees of given ranks r1 and r2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The explicit mapping from trees to permutations and bivariate polynomials may supply algebraic tools for proving further structural properties of rotation sequences.
Because the quadratic upper bound is tight already at rank 1, the dependence on rank in the general bound cannot be improved without changing the leading n squared factor.
The reduction isolates the combinatorial difficulty of high-rank intermediate trees, suggesting that hardness results for the general problem, if they exist, must arise from sequences that temporarily increase rank.

Load-bearing premise

The polynomial-time reduction from the unrestricted rotation distance problem to the rank-bounded version preserves the numerical value of the distance.

What would settle it

Two binary trees whose shortest unrestricted rotation sequence is forced to pass through an intermediate tree whose rank exceeds the bound used in the reduction, or a pair of skew trees whose distance exceeds n squared.

Figures

Figures reproduced from arXiv: 2304.03985 by Anoop S. K. M., Jayalal Sarma.

**Figure 1.** Figure 1: Right rotation at node ”a” The new tree is identical except that the subtree at ”a” is replaced with the following tree: the root is ”b”, the left (resp. right) child of ”b” is ”C”, the right (resp. left) child of ”b” is ”a”, the left (resp. right) child of ”a” is ”D”, and the right (resp. left) subtree of ”a” is ”E”. The rotation distance between two full binary trees T1 and T2 is the minimum number of ro… view at source ↗

**Figure 2.** Figure 2: Proof of Lemma 3.2 by applying a left rotation at x. We observe that only one element (y) gets shifted, while the relative ordering of others remain the same. Hence this operation correspond to a 1-transposition. ⊓⊔ Now we prove the equivalence by way of counting the number of tree transpositions and 1- transpositions separately (see Lemma 3.3 and Lemma 3.4) and hence conclude the proof of Theorem 1.7. Le… view at source ↗

**Figure 3.** Figure 3: Two distinct full binary trees with same tree polynomial. Here [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗

read the original abstract

Computing the rotation distance between two binary trees with $n$ internal nodes efficiently (in $poly(n)$ time) is a long standing open question in the study of height balancing in tree data structures. In this paper, we initiate the study of this problem bounding the rank of the trees given at the input (defined by Ehrenfeucht and Haussler (1989) in the context of decision trees). We define the rank-bounded rotation distance between two given binary trees $T_1$ and $T_2$ (with $n$ internal nodes) of rank at most $r$, denoted by $d_r(T_1,T_2)$, as the length of the shortest sequence of rotations that transforms $T_1$ to $T_2$ with the restriction that the intermediate trees must be of rank at most $r$. We show that the rotation distance problem reduces in polynomial time to the rank bounded rotation distance problem. This motivates the study of the problem in the combinatorial and algorithmic frontiers. Observing that trees with rank $1$ coincide exactly with skew trees (binary trees where every internal node has at least one leaf as a child), we show the following results in this frontier : We present an $O(n^2)$ time algorithm for computing $d_1(T_1,T_2)$. That is, when the given trees are skew trees (we call this variant as skew rotation distance problem) - where the intermediate trees are restricted to be skew as well. In particular, our techniques imply that for any two skew trees $d(T_1,T_2) \le n^2$. We show the following upper bound : for any two trees $T_1$ and $T_2$ of rank at most $r_1$ and $r_2$ respectively, we have that: $d_r(T_1,T_2) \le n^2 (1+(2n+1)(r_1+r_2-2))$ where $r = max\{r_1,r_2\}$. This bound is asymptotically tight for $r=1$. En route our proof of the above theorems, we associate binary trees to permutations and bivariate polynomials, and prove several characterizations in the case of skew trees.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines rank-bounded rotation distance, claims a poly-time reduction from the general case, and gives an O(n^2) algorithm plus tight bound for skew trees, but the reduction's distance preservation is the part that needs the full construction to confirm.

read the letter

The main takeaway is that this paper restricts rotation distance to rank-bounded trees, shows a polynomial reduction from the unrestricted problem, and then solves the rank-1 case exactly with an O(n^2) algorithm while proving a matching upper bound of O(n^2) for skew trees. They also give a general upper bound of n^2 (1 + (2n+1)(r1 + r2 - 2)) that is tight at r=1. They link skew trees to permutations and bivariate polynomials along the way to get characterizations. That association and the explicit algorithm for the skew case are the concrete new pieces. The reduction is the part that stands out as potentially useful if it holds, since it would let bounded-rank results speak to the open general problem. The bound and algorithm look like solid restricted-case progress. The soft spot is exactly the reduction step. The abstract states that the general problem reduces in poly time to the rank-bounded version, but to carry over to the open question the mapping has to produce instances where the shortest rotation sequence stays inside the rank bound and the distances match exactly. If any shortest path in the original trees requires higher-rank intermediates, then d_r could be strictly larger. The stress-test note flags this correctly, and the abstract gives no details on the construction or recovery, so that claim sits on the proofs. No other internal contradictions show up in the stated results. The work is aimed at people who already care about rotation distance or algorithms on binary trees. A reader looking for new angles on a long-open problem will find the restricted algorithm and the polynomial association worth seeing. It deserves a serious referee because it supplies a fresh formulation plus verifiable algorithmic results on a concrete subclass, even if the reduction needs checking.

Referee Report

2 major / 0 minor

Summary. The paper claims a polynomial-time reduction from the general rotation distance problem on binary trees to its rank-bounded variant. For rank-1 (skew) trees it gives an O(n²)-time algorithm computing the restricted distance d₁(T₁,T₂) and deduces that the unrestricted distance satisfies d(T₁,T₂)≤n². It also proves the combinatorial upper bound dᵣ(T₁,T₂)≤n²(1+(2n+1)(r₁+r₂-2)) where r=max{r₁,r₂}, shown to be asymptotically tight for r=1. The arguments associate trees with permutations and bivariate polynomials and supply characterizations for the skew case.

Significance. If the reduction is correct, the work supplies a concrete algorithmic and combinatorial foothold on the long-standing open problem of computing rotation distance in polynomial time. The O(n²) algorithm for skew trees is efficient, the upper bound is tight for the base case r=1, and the permutation/polynomial associations may furnish reusable tools for restricted rotation-distance questions.

major comments (2)

[Abstract] Abstract: the central claim that unrestricted rotation distance reduces in polynomial time to the rank-bounded problem requires an explicit mapping T₁,T₂↦T₁′,T₂′ together with a proof that the shortest rotation sequence length is exactly preserved (or recoverable in poly time) while every intermediate tree stays inside the stated rank bound. Without this construction the subsequent O(n²) algorithm and the O(n³r) bound cannot be transferred to the unrestricted problem.
[Upper bound paragraph] The upper-bound statement (and its claimed asymptotic tightness for r=1): the derivation must be checked against the precise definition of rank (Ehrenfeucht–Haussler) and against the permutation/polynomial encoding to confirm that the factor (2n+1)(r₁+r₂-2) is not an artifact of an overly loose counting argument.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below.

read point-by-point responses

Referee: [Abstract] Abstract: the central claim that unrestricted rotation distance reduces in polynomial time to the rank-bounded problem requires an explicit mapping T₁,T₂↦T₁′,T₂′ together with a proof that the shortest rotation sequence length is exactly preserved (or recoverable in poly time) while every intermediate tree stays inside the stated rank bound. Without this construction the subsequent O(n²) algorithm and the O(n³r) bound cannot be transferred to the unrestricted problem.

Authors: The manuscript provides the explicit polynomial-time reduction (via the permutation association) and the distance-preservation argument in the body of the paper. We agree the abstract is too brief on this point and will revise it to state the mapping and the exact preservation property. revision: yes
Referee: [Upper bound paragraph] The upper-bound statement (and its claimed asymptotic tightness for r=1): the derivation must be checked against the precise definition of rank (Ehrenfeucht–Haussler) and against the permutation/polynomial encoding to confirm that the factor (2n+1)(r₁+r₂-2) is not an artifact of an overly loose counting argument.

Authors: The derivation follows directly from the Ehrenfeucht–Haussler rank definition and the bivariate-polynomial encoding: each rank adjustment costs at most 2n+1 rotations and there are r₁+r₂−2 such adjustments, multiplied by the quadratic base bound. Asymptotic tightness for r=1 is shown by explicit skew-tree constructions requiring Ω(n²) rotations, so the factor is not loose. revision: no

Circularity Check

0 steps flagged

No circularity: algorithmic reduction, explicit algorithm, and combinatorial bound are self-contained

full rationale

The paper defines d_r(T1,T2) explicitly as the shortest rotation sequence length under the rank-at-most-r restriction on all intermediate trees. It then claims a polynomial-time reduction from unrestricted rotation distance to this d_r problem, presents an O(n²) algorithm for the r=1 (skew) case, and derives the combinatorial upper bound d_r ≤ n²(1+(2n+1)(r1+r2-2)) via explicit associations of trees to permutations and bivariate polynomials. No step equates a claimed result to a fitted parameter, renames a known quantity, or reduces via self-citation to an unverified premise; the reduction, algorithm, and bound are constructed directly from the definitions and characterizations without circular dependence on their own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard definition of tree rank from prior literature and the combinatorial properties of rotations; no free parameters or new entities are introduced.

axioms (2)

domain assumption The rank of a binary tree is defined as in Ehrenfeucht and Haussler (1989).
Invoked to define the input restriction and the intermediate-tree constraint.
standard math Rotations preserve the inorder traversal of the binary tree.
Standard background fact used in all rotation-distance definitions.

pith-pipeline@v0.9.0 · 5959 in / 1551 out tokens · 42157 ms · 2026-05-24T09:12:04.534818+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

Learning decision trees from random examples

Ehrenfeucht A, Haussler D. Learning decision trees from random examples. Information and Computa- tion, 1989. 82(3):231–246. doi:10.1016/0890-5401(89)90001-1

work page doi:10.1016/0890-5401(89)90001-1 1989
[2]

Polynomials, Binary Trees, and Positive Braids

Wiley C, Gray J. Polynomials, Binary Trees, and Positive Braids. Missouri Journal of Mathematical Sciences, 2014. 26(1):1–13. doi:10.35834/mjms/1404997104

work page doi:10.35834/mjms/1404997104 2014
[3]

A note on some tree similarity measures

Culik K, Wood D. A note on some tree similarity measures. Information Processing Letters , 1982. 15(1):39–42. doi:10.1016/0020-0190(82)90083-7

work page doi:10.1016/0020-0190(82)90083-7 1982
[4]

On the rotation distance between binary trees

Dehornoy P. On the rotation distance between binary trees. Advances in Mathematics, 2010. 223(4):1316–

work page 2010
[5]

doi:10.1016/j.aim.2009.09.016

work page doi:10.1016/j.aim.2009.09.016 2009
[6]

Rotation Distance, Triangulations, and Hyperbolic Geometry

Sleator D, Tarjan R, Thurston W. Rotation Distance, Triangulations, and Hyperbolic Geometry. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing. 1986 1(3):122–135. doi:10.1145/12130.12143

work page doi:10.1145/12130.12143 1986
[7]

The diameter of associahedra

Pournin L. The diameter of associahedra. Advances in Mathematics, 2014. 259:13–42

work page 2014
[8]

A Linear-Time Approximation Algorithm for Rotation Distance

Cleary S, John KS. A Linear-Time Approximation Algorithm for Rotation Distance. J. Graph Algorithms Appl., 2010. 14(2):385–390. doi:10.7155/jgaa.00212. 104 S.K.M. Anoop and J. Sarma / On Rotation Distance of Rank Bounded Trees

work page doi:10.7155/jgaa.00212 2010
[9]

Untangling Binary Trees via Rotations

Lucas J. Untangling Binary Trees via Rotations. The Computer Journal , 2004. 47(2):259–269. doi:10. 1093/comjnl/47.2.259

work page 2004
[10]

The Rotation Graph of Binary Trees Is Hamiltonian

Lucas J. The Rotation Graph of Binary Trees Is Hamiltonian. Journal of Algorithms, 1987. 8(4):503–535. doi:10.1016/0196-6774(87)90048-4

work page doi:10.1016/0196-6774(87)90048-4 1987
[11]

Linear-Time Constant-Ratio Approximation Algorithm and Tight Bounds for the Contiguity of Cographs

Crespelle C, Gambette P. Linear-Time Constant-Ratio Approximation Algorithm and Tight Bounds for the Contiguity of Cographs. In: W ALCOM: Algorithms and Computation, 7th International Workshop, W ALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings, volume 7748 ofLecture Notes in Computer Science. Springer, 2013 pp. 126–136

work page 2013
[12]

In: Proc

Bulteau L, Fertin G, Rusu I. Sorting by Transpositions Is Difficult. In: Proceedings of International Con- ference on Automata, Languages and Programming (ICALP 2011). 2011 pp. 654–665. doi:10.1007/978- 3-642-22006-7 55

work page doi:10.1007/978- 2011

[1] [1]

Learning decision trees from random examples

Ehrenfeucht A, Haussler D. Learning decision trees from random examples. Information and Computa- tion, 1989. 82(3):231–246. doi:10.1016/0890-5401(89)90001-1

work page doi:10.1016/0890-5401(89)90001-1 1989

[2] [2]

Polynomials, Binary Trees, and Positive Braids

Wiley C, Gray J. Polynomials, Binary Trees, and Positive Braids. Missouri Journal of Mathematical Sciences, 2014. 26(1):1–13. doi:10.35834/mjms/1404997104

work page doi:10.35834/mjms/1404997104 2014

[3] [3]

A note on some tree similarity measures

Culik K, Wood D. A note on some tree similarity measures. Information Processing Letters , 1982. 15(1):39–42. doi:10.1016/0020-0190(82)90083-7

work page doi:10.1016/0020-0190(82)90083-7 1982

[4] [4]

On the rotation distance between binary trees

Dehornoy P. On the rotation distance between binary trees. Advances in Mathematics, 2010. 223(4):1316–

work page 2010

[5] [5]

doi:10.1016/j.aim.2009.09.016

work page doi:10.1016/j.aim.2009.09.016 2009

[6] [6]

Rotation Distance, Triangulations, and Hyperbolic Geometry

Sleator D, Tarjan R, Thurston W. Rotation Distance, Triangulations, and Hyperbolic Geometry. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing. 1986 1(3):122–135. doi:10.1145/12130.12143

work page doi:10.1145/12130.12143 1986

[7] [7]

The diameter of associahedra

Pournin L. The diameter of associahedra. Advances in Mathematics, 2014. 259:13–42

work page 2014

[8] [8]

A Linear-Time Approximation Algorithm for Rotation Distance

Cleary S, John KS. A Linear-Time Approximation Algorithm for Rotation Distance. J. Graph Algorithms Appl., 2010. 14(2):385–390. doi:10.7155/jgaa.00212. 104 S.K.M. Anoop and J. Sarma / On Rotation Distance of Rank Bounded Trees

work page doi:10.7155/jgaa.00212 2010

[9] [9]

Untangling Binary Trees via Rotations

Lucas J. Untangling Binary Trees via Rotations. The Computer Journal , 2004. 47(2):259–269. doi:10. 1093/comjnl/47.2.259

work page 2004

[10] [10]

The Rotation Graph of Binary Trees Is Hamiltonian

Lucas J. The Rotation Graph of Binary Trees Is Hamiltonian. Journal of Algorithms, 1987. 8(4):503–535. doi:10.1016/0196-6774(87)90048-4

work page doi:10.1016/0196-6774(87)90048-4 1987

[11] [11]

Linear-Time Constant-Ratio Approximation Algorithm and Tight Bounds for the Contiguity of Cographs

Crespelle C, Gambette P. Linear-Time Constant-Ratio Approximation Algorithm and Tight Bounds for the Contiguity of Cographs. In: W ALCOM: Algorithms and Computation, 7th International Workshop, W ALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings, volume 7748 ofLecture Notes in Computer Science. Springer, 2013 pp. 126–136

work page 2013

[12] [12]

In: Proc

Bulteau L, Fertin G, Rusu I. Sorting by Transpositions Is Difficult. In: Proceedings of International Con- ference on Automata, Languages and Programming (ICALP 2011). 2011 pp. 654–665. doi:10.1007/978- 3-642-22006-7 55

work page doi:10.1007/978- 2011