Left-size potential of a binary tree
ID: left-size-potential-of-a-binary-tree
Define and . 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.
New to topics? Read the docs here!