Rotation of full binary trees (every internal node has exactly two children, here we refer to such trees as simply binary trees) is an important operation due to their classical applications in data structures. A right(left) rotation of a full binary tree at an internal node consists of rotating the right(left) child of the left(right) child of the node to the left(right) child of the node. The rotation distance between two rooted binary trees with the same number of leaves (and hence the same number of internal nodes) is the minimum number of rotations needed to transform one tree to the other. The combinatorial problem of how far two binary trees can be, in terms of rotation distance, has already been precisely characterized in the literature. The main computational question we are interested in here is, given two trees with same number of nodes, compute the rotation distance between them. The decision version of this question asks, given two trees and a value k, whether the rotation distance at most k or not. While there have been results about approximation and fixed-parameter tractable algorithms for the problem, it is not even known whether the problem is NP-complete or not.

In this work, we associate binary trees to permutations and relate the rotation operation on trees to transpositions in the corresponding permutations. A transposition in an operation on a
permutation (in general on any sequence of numbers) that consists of swapping two consecutive subsequences of the permutation. This is motivated by the fact that, in a recent resolution of an open
the problem, the problem of computing the transposition distance in general, between two permutations, has been shown to be NP-hard. While this does not directly establish the hardness for the rotation distance problem in general, as our technical contributions, we will present the following positive results: we characterize permutations that correspond to binary trees and skew binary trees (binary trees where every internal node has at least one leaf as a child) under this association. Using this characterization, and their reinterpretations as binary strings, we give a polynomial-time algorithm, which given two trees, computes the skew rotation distance between them (rotation distance where intermediate trees must also be skew). Notice that, a priori it is not even clear if a skew tree can be transformed into another skew tree through a sequence of rotations retaining the skewness property of the tree. We also exactly characterize the transpositions that correspond to the set of rotations in binary trees.