Show that
O
(
n
) rotations suffice to convert any binary tree into a
left chain
, where each internal node has an external right child.