= Solution
For a remaining tree $T$, define the potential
$$
L(\varnothing)=0,\qquad L(T)=|T.left|+L(T.right).
$$
This counts the nodes not on the right spine, so $0\leq L(T)\leq |T|$. Consider a <right rotation> with old root $y$, left child $x$, and three untouched <subtrees> $A,B,C$. Before the rotation the potential is
$$
1+|A|+|B|+L(C).
$$
After the rotation it is $|A|+|B|+L(C)$, so \b[each rotation decreases $L$ by exactly one] while preserving the number of remaining nodes. This supplies a nonnegative decreasing bound for the inner loop.
When the root has no left child, printing it and advancing to its right child leaves $L$ unchanged and decreases the remaining node count by one. Thus $|T|+L(T)$ decreases on every rotation and every removal, proving termination of the whole procedure. Over the entire execution there are exactly $N$ printed nodes and exactly $L(T_0)$ rotations, since the final potential is zero. Both quantities are at most $N$, so \b[the running time is $\Theta(N)$ for a nonempty tree], with constant <auxiliary space>. The nested syntax does not imply quadratic time: it is the total potential decrease across all iterations that bounds the inner work. The potential is a proof device and is not computed by the running program.
Back to article page
