= Destructive inorder traversal by right rotations
While the remaining root has a left child, apply a <right tree rotation> there. Once the left child is null, output the root and advance to its right child. The output already produced followed by the remaining inorder <sequence> is <invariant>. There are exactly $N$ output removals and $L(T_0)\leq N$ rotations, because rotations decrease the left-size potential and removals preserve it. The <algorithm> therefore takes linear time and constant auxiliary pointer space, at the cost of changing the input links.
Back to article page
