= Solution
Let $s(T)$ be the number of nodes and let the <left-size potential of a binary tree> be
$$
L(\varnothing)=0,\qquad L(T)=s(T.left)+L(T.right).
$$
Equivalently $L(T)$ counts nodes outside the right spine, so $0\leq L(T)\leq s(T)$; for a nonempty <binary tree> of $n$ nodes, $L(T)\leq n-1$.
For the <right tree rotation> in part (f), write the old shape as $((A,x,B),y,C)$. Before and after,
$$
L_{\rm before}=s(A)+1+s(B)+L(C),\qquad
L_{\rm after}=s(A)+s(B)+L(C).
$$
Thus each inner iteration decreases $L$ by exactly one, making $L$ an inner <loop variant>. Removing a root with empty left <subtree> leaves $L$ unchanged and decreases $s$ by one. Therefore $s+L$ decreases on every rotation or visit, while $s$ decreases on every completed outer iteration. These are bounds used for proof; the program never computes them.
There are exactly $n$ visits and exactly $L(T_0)$ rotations, since the final empty <binary tree> has potential zero. Counting constant-cost `p`,
$$
\boxed{\text{rotations}+\text{visits}=n+L(T_0)\leq2n-1\quad(n>0),\qquad T(n)=\Theta(n+1).}
$$
The nested loops therefore have linear total <running time>, despite one outer iteration potentially making many rotations.
Back to article page
