Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 1 / g

Let $s(T)$ be the number of nodes and let the left-size potential of a binary tree beEquivalently $L(T)$ counts nodes outside the right spine, so $0\le L(T)\le s(T)$; for a nonempty binary tree of $n$ nodes, $L(T)\le n-1$.

For the right tree rotation in part (f), write the old shape as $((A,x,B),y,C)$. Before and after,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,The nested loops therefore have linear total running time, despite one outer iteration potentially making many rotations.