Make v the root of its tree (reverse all edges on path from v to current root):
function makeRoot(v)
access(v)
// Reverse the auxiliary tree (flip all edges)
v.reversed := not v.reversed
pushDown(v)
You use lazy propagation: mark the auxiliary tree as "reversed" without reversing. Push down the reversal flag when accessing children.
function pushDown(v)
if v.reversed then
swap(v.left, v.right)
if v.left then v.left.reversed := not v.left.reversed
if v.right then v.right.reversed := not v.right.reversed
v.reversed := false
Time: amortized.