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!