  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.
