Practical estimation of rotation distance
and induced partial order for binary trees
Jarek Duda

arXiv:1610.06023v1 [] 19 Oct 2016

Jagiellonian University, Golebia 24, 31-007 Krakow, Poland. Email: dudajar@gmail.com

Abstract—Tree rotations (left and right) are basic local deformations allowing to transform between two unlabeled binary
trees of the same size. Hence, there is a natural problem of
practically finding such transformation path with low number
of rotations, the optimal minimal number is called the rotation
distance. Such distance could be used for instance to quantify similarity between two trees for various machine learning problems,
for example to compare hierarchical clusterings or arbitrarily
chosen spanning trees of two graphs, like in SMILES notation
popular for describing chemical molecules.
There will be presented inexpensive practical greedy algorithm
for finding a short rotation path, optimality of which has still to
be determined. It uses introduced partial order for binary trees
of the same size: t1 ≤ t2 iff t2 can be obtained from t1 by a
sequence of only right rotations. Intuitively, the shortest rotation
path should go through the least upper bound or the greatest
lower bound for this partial order. The algorithm finds a path
through candidates for both points in representation of binary
tree as stack graph: describing evolution of content of stack
while processing a formula described by a given binary tree.
The article is accompanied with Mathematica implementation of
all used procedures (Appendix).

Keywords: tree rotation, algorithmics, machine learning
I. I NTRODUCTION
Tree is a basic tool of computer science, used for example
to represent hierarchical structure in data, e.g. in hierarchical
clustering [1]. It is a natural question to evaluate similarity between such trees, maybe propose a path of local deformations
to get a transformation between such two structures. A natural
candidate for the required elementary local deformation of a
binary tree, maintaining order of leaves, are tree rotations (left
and right), which switch levels of two nodes and reconnect
their subtrees. It is used for example to balance binary search
tree in popular AVL method [2].
The minimal number of rotations to transform between
two binary trees is a metric called rotation distance. It was
shown that for any two N -node trees, for n ≥ 11, this
distance is at most 2N − 6 and there exist pairs of trees
fulfilling this 2N − 6 distance ([3], [4]). Binary trees have
multiple equivalent representations, for example as bracketing
or triangularization of polygon used in these two cited articles.
There will be discussed greedy algorithm for finding a rotation path which base on a different representation: of evolution
of stack content while processing such bracketed formula,
which can be found for example in Chapter 7 of ”Concrete
mathematics” book [5]. We will refer to this function as stack
graph, it is visualized if Fig. 1 and left/right rotations become

Figure 1. An example of binary tree (top), corresponding bracketing (center)
and stack graph (bottom): describing evolution of content of stack while
processing a formula described by a given binary tree (bracketing). It can
be obtained by post-order tree traversal: visiting leaf corresponds to +1 for
the graph (’x’ in bracketing, push value to stack), visiting internal node to -1
(closing bracket: pop two values then push their function).

simple lower/lift procedures, visualized in Fig. 2, which turn
out convenient for searching for a short path.
This representation allows to conclude that a natural relation
is a partial order: t1 ≤ t2 iff there exists a series of right
rotations transforming tree t1 to t2 . This partial order for 4
and 5 node trees is presented in Fig. 3 and 4. These figures

evaluating distance between different hierarchical clusterings.
Another example of situation where we need to quickly evaluate distance between trees is for comparing graphs for which
we can define a spanning tree in an unique way. We cannot do
it for general graphs, as it would solve the graph isomorphism
problem, but such spanning trees are a popular tool to describe
e.g. chemical molecules in so called SMILES notation [6].
Such trees are more complex than binary unlabeled: degree of
nodes can be larger than two and both vertices and edges may
have types worth including in the definition of distance - will
require a generalization of the discussed method.
II. PARTIAL ORDER AND
GREEDY SEARCH FOR COMMON LIFT
Denote the set of all n-leaf unlabeled binary trees as Tn ,
|Tn | = 2n−2
n−1 /n is Catalan number. Each of such trees has
n − 1 internal nodes of degree 2, denote the number of all its
nodes as N = 2n − 1.
Let us define its stack graph as in Fig. 1:
Figure 2. Tree rotations (left) and their analogue for corresponding bracketing
(gray) and stack graph (right). The α, β and γ are nonegative graphs of even
width (can be zero), changing by ±1 per position. Presented lift will be
denoted by lij , where i, j are the marked positions.

Figure 3. Partial order for all 4 leaf binary trees (top) and their stack graphs
(bottom). Each arrow denotes possibility of single right rotation (or lift).

suggest that the shortest path between two trees has to go
through their least upper bound (∧) or their greatest lower
bound (∨) for this order, or in other words: the path can be
chosen (sorted) as first a sequence of right rotations, then of
left rotations (∧) or oppositely (∨). However, this intuition has
still to be verified.
There will be presented a natural inexpensive (O(n ·
’path length’)) greedy algorithm to find the common lift (CL)
for stack graphs of two trees, which corresponds to a candidate
for the least upper bound (∧) of these trees. By taking mirror
image of the trees, which switches left and right rotations
and so reverses the order, this algorithm can also provide a
candidate for the greatest lower bound (∨). Its optimality has
still to be verified, but currently it can be used to quickly find
the upper bound for the rotation distance or to approximate
this distance and find a short path, especially for situations
where the optimality is not crucial.
For example for various machine learning situations, like

Definition 1. Stack graph st : {0, . . . , N } → N for tree t ∈
Tn is function defined by the following conditions:
• st (0) = 0, st (N ) = 1,
• for i = 1, . . . , N , st (i) − st (i − 1) = 1 if i-th node in
post-order traversal of t is leaf, −1 otherwise
Stack graph is fixed for 0 and 1, and is at least 1 for i ∈
{1, . . . , N }. For better visualization, it will be depictured with
points joined by lines, sometimes without the fixed [0, 1] range
(Fig. 3, 4). Denote Sn = s(Tn ) as the set of all stack graphs
for n-leaf binary trees.
The tree rotation operations are presented in Fig. 2. In bracketing notation, right rotation changes ((αβ)γ) into (α(βγ))
and left rotation the opposite, where α, β, γ represent some
formulas (subtrees), which can be degenerated into single
variables (leaves).
As we can see in this figure, right rotation corresponds
to lift by (−1, 1) vector of some {i, . . . , j} range. It can be
degenerated: i = j for leaves.
Definition 2. For two stack graphs: s1 , s2 ∈ Sn we will say
that s2 is (i, j) lift of s1 , denoted as s2 = lij (s1 ), if the
following conditions are fulfilled:
1) i ≤ j, s1 (i) = s1 (j)
2) s1 (i − 1) = s1 (i + 1) = s1 (j − 1) = s(i) + 1
3) for i < k < j, s1 (k) > s1 (i)
4) for k < i and j < k, s1 (k) = s2 (k)
5) for i ≤ k ≤ j, s2 (k − 1) = s1 (k) + 1
The value of stack graph will be referred as level. Condition
1) says that i ≤ j are on the same level of s1 , 2) says that
there is first ’∨’ shape in i, then ’\’ shape in j. Condition 3)
enforces s1 being above the i, j level. Finally 4) and 5) say
that s1 and s2 differ only on the [i, j] range, in which s2 is
lift by (−1, 1) vector of s1 .
Obviously, lifting cannot decrease value in any position:
Observation 3. If t2 is a right rotation of t1 , then for all
i ∈ {0, . . . , N }, st1 (i) ≤ st2 (i).

Figure 4. Partial order for all 5 leaf binary trees (top) and their stack graphs (bottom). Each arrow denotes possibility of single right rotation (or lift). Observe
symmetry of the top diagram - taking mirror image of all trees switches left and right rotation, reversing the order

It allows to conclude antisymmetry of the following relation,
its reflexivity and transitivity are obvious, making it a partial
order in Tn :
Definition 4. For t1 , t2 ∈ Tn we define partial order: t1 ≤ t2
iff t1 = t2 or there exists a sequence of right rotations from
t1 to t2 .
Examples of this partial order for 4 and 5 leaf trees are
presented in Fig. 3 and 4 correspondingly. These examples
suggest that the shortest rotation path has to go through the
least upper bound (∧) or the greatest lower bound (∨), however, it does not have to be generally true. Having algorithm
searching for a short path going through the least upper bound
(∧), we could use it to find path going through the greatest
lower bound (∨) by taking mirror images of both trees, which
switch left and right rotations, reversing this order. There is
a nontrivial relation between stack graph of a tree and of its
mirror image, which examples are presented in various figures
of this paper, but it can found in O(n) time and memory (see
mirror[] in Appendix).
To find a candidate of the the greatest lower bound, we can
take both stack graphs and use a sequence of lifts applied to a
locally lower one, to finally equalize them, getting a candidate
for the lowest common lift and of path to them. Example of
such process is presented in Fig. 5. It is presented (without
tracking the changes) as Algorithm 1 and 2.
Its naive implementation (see findrotationpath[] in
Appendix) is linear in n and path length. Figure 7 shows

Figure 5. Example of finding a common lift using the greedy algorithm.
Its step finds the lowest level where the two stack graphs disagree, find the
most-right position of such points in this level (i), find the closest position in
this level right to this point (j), then lift (i, j) segment. Such steps continue
until equalizing both stack graphs, getting a common lift.

examples of common lifts found by this algorithm, Figure 8
shows example of found rotation path for tree with 30 leaves.
III. C ONCLUSIONS AND FURTHER PERSPECTIVES
There was presented a practical way to search for a short
rotation path between two unlabeled binary trees of the same
size. Its optimality is not guaranteed in this moment, nor
counterexamples were found. It can be used to find a rotation
path and bound from above or approximate the rotation path.

Algorithm 1 Greedy common lift for s1, s2 stack graphs
while s1 6= s2 do
lvl = min{s1[k] : s1[k] 6= s2[k]}
i = max{k : s1[k] 6= s2[k], lvl = min(s1[k], s2[k])}
if s1[i] < s2[i] then
j = min{k > i: s1[k] = lvl}; lift(s1,i,j)
else
j = min{k > i: s2[k] = lvl}; lift(s2,i,j)
end if
end while
Algorithm 2 Greedy shortest path for s1, s2
find common lift for s1 and s2
find common lift for mirror(s1) and mirror(s2)
take the shorter one

The basic question to investigate is optimality of this algorithm. If it is not optimal, maybe find its improvements, find
bounds for its inaccuracy, try to characterise counterexamples.
If it is already optimal, the proof might go through the
following steps, each of which might turn out false:
1) The shortest rotation path has to go through the least
upper bound or the greatest lower bound of the two
trees. In other words, the shortest rotation path can be
chosen (sorted) as only right rotations first then only left
rotations, or oppositely,
2) The common lift found by the greedy algorithm corresponds to the least upper bound,
3) The greedy algorithm finds the shortest path to the
obtained common lift - the number of lifts cannot be
reduced.
Another large topic is applying this or extended methods for
various problems, especially in machine learning, where not
being optimal seems not crucial. There will be needed some
expansions, like generalization to non-binary trees, which can
be realized for example by splitting a higher degree node into
a few binary nodes. Also, in some applications we should
distinguish types of nodes and edges (e.g. atoms and molecular
bonds), which might require modifying the metric and so the
optimization problem.
A related line of work is trying to apply this method
to evaluate similarity of graphs by comparing some their
arbitrarily chosen spanning trees. Choosing an isomorphism
independent spanning tree is generally a difficult problem,
as it would allow to solve the graph isomorphism problem.
However, it can be useful for some families of graphs, used
for example in SMILES representation of chemical molecules.
A PPENDIX
This appendix contains Wolfram Mathematica sources used
to generate figures in this article. It generates random binary
tree assuming uniform probability distribution among trees of
given number of leaves. For this purpose, it uses enumerative
decoding [7] to get a random sequence of +1 and -1 which
sums to 1, then finds its only cyclic rotation giving a stack
graph.

(* enumerative decoding *)
dec[n_, w_, X_] := (l = w; x = X;
Table[b = Binomial[n - i, l];
If[x < b, 0, x -= b; l--; 1], {i, n}]);
(* generate stack graph of n leaf random tree *)
randtree[n_] := (nn = 2 n - 1;
s = 2 dec[2 n - 1, n,
RandomInteger[Binomial[2 n - 1, n - 1] - 1]] - 1;
Do[s[[i]] += s[[i - 1]], {i, 2, nn}];
min = Min[s];
div = Max[Table[If[s[[i]] == min, i, 0], {i, nn}]];
Join[s[[div ;; nn]], 1 + s[[1 ;; div]]] - min);
(* draw tree from stack graph *)
drawtree[s_] := (st = Table[0, {i, Length[s]}];
stp = 1; vn = 1; edg = {};
Do[If[s[[i + 1]] - s[[i]] == 1, st[[stp++]] = vn++,
AppendTo[edg,
{st[[stp - 2]] -> vn, st[[stp - 1]] -> vn}];
st[[stp - 2]] = vn++; stp--], {i, 1, Length[s] - 1}];
TreePlot[Sort[Flatten[edg]], Automatic, Length[s] - 1,
VertexLabeling -> False]);
(* mirror image of tree from stack graph *)
mirror[s_] := (ls = Length[s]; p = 0;
pbr = Table[i, {i, ls/2}]; nbr = Table[0, {i, ls/2}];
Do[If[s[[i + 1]] - s[[i]] == 1, p++,
brac = pbr[[pbr[[p]] - 1]];
nbr[[pbr[[p]] = brac]]++], {i, ls - 1}];
S = Table[0, {i, ls}]; p = 1;
Do[p++; S[[p]] = S[[p - 1]] + 1;
Do[p++; S[[p]] = S[[p - 1]] - 1, {j, 1, nbr[[i]]}]
,{i, ls/2, 1, -1}]; S);
(* the greedy algorithm to find path *)
lift[s_, f_, t_] :=
Join[s[[1 ;; f - 1]], s[[f + 1 ;; t]] + 1, {s[[t]]},
s[[t + 1 ;; Length[s]]]];
findrotationpath[S1_, S2_] := (
s1 = S1; s2 = S2; ll = {s1}; rl = {s2};
While[s1 != s2, min = Infinity;
Do[If[s1[[i]] != s2[[i]], m = Min[s1[[i]], s2[[i]]];
If[m <= min, min = m; pm = i]], {i, Length[s1]}];
px = pm + 2;
If[s1[[pm]] < s2[[pm]],
While[s1[[px]] > min, px++];
AppendTo[ll, s1 = lift[s1, pm, px]],
While[s2[[px]] > min, px++];
PrependTo[rl, s2 = lift[s2, pm, px]]]];
Join[ll, rl[[2 ;; Length[rl]]]])
(* example of application *)
n = 10; S1 = randtree[n]; S2 = randtree[n];
path1 = findrotationpath[S1, S2];
path2 = findrotationpath[mirror[S1], mirror[S2]];
Print[Row[Table[drawtree[path1[[i]]], {i, Length[path1]}]]]
Row[Table[drawtree[path2[[i]]], {i, Length[path2]}]]

R EFERENCES
[1] J. H. Ward Jr, “Hierarchical grouping to optimize an objective function,”
Journal of the American statistical association, vol. 58, no. 301, pp. 236–
244, 1963.
[2] G. Adelson-Velsky and E. Landis, “An algorithm for the organization of
information,” Proceedings of the USSR Academy of Sciences, vol. 146,
pp. 263–266, 1962.
[3] D. D. Sleator, R. E. Tarjan, and W. P. Thurston, “Rotation distance,
triangulations, and hyperbolic geometry,” Journal of the American Mathematical Society, vol. 1, no. 3, pp. 647–681, 1988.
[4] L. Pournin, “The diameter of associahedra,” Advances in Mathematics,
vol. 259, pp. 13–42, 2014.
[5] D. E. Knuth, R. L. Graham, O. Patashnik et al., “Concrete mathematics,”
Adison Wesley,, 1989.
[6] D. Weininger, “Smiles, a chemical language and information system. 1.
introduction to methodology and encoding rules,” Journal of chemical
information and computer sciences, vol. 28, no. 1, pp. 31–36, 1988.
[7] L. Oktem, Hierarchical enumerative coding and its applications in image
compression. Tampere University of Technology, 1999.

Figure 6. Example of rotation path found by the greedy algorithm for common lift, for the original trees (top) and their mirror images (bottom). The marked
trees correspond to the common lift. The upper path is shorter so it will be the final answer.

Figure 7. Five examples (columns) of the found common lift by greedy algorithm (highest orange line) for stack graphs of two random trees (lower: blue
and green lines). The upper row corresponds to stack graphs of the original trees: common lift is a candidate for the least upper bound. The lower row
corresponds to stack graphs of mirror images of the trees.

Figure 8.

Example of found rotation path for two random 30 vertex trees. The marked tree corresponds to the common lift.

