= Left-size potential of a binary tree
{title2=$L(T)=|T.left|+L(T.right)$}
Define $L(\varnothing)=0$ and $L(T)=|T.left|+L(T.right)$. Subtracting the right-spine length from total size gives the same quantity, because every node lies either on that spine or in one of its disjoint left <subtrees>. A <right tree rotation> at the root decreases this potential by exactly one; removing a root with no left child preserves it. Thus repeated root rotations and inorder removals take linear total work.
Back to article page
