Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 5 / d / Solution

For a remaining tree $T$, define the potentialThis counts the nodes not on the right spine, so $0\le L(T)\le |T|$. Consider a right rotation with old root $y$, left child $x$, and three untouched subtrees $A,B,C$. Before the rotation the potential isAfter the rotation it is $|A|+|B|+L(C)$, so 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 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.