AVL rotation pseudocode that finally worked for me

My own pseudocode notes for rotations. Writing them this way stopped my pointer bugs. rotateLeft(node): newRoot = node.right node.right = newRoot.left newRoot.left = node update height and balance factor of node, then newRoot return newRoot rotateRight is the mirror image. rebalance(node): if balance(node) == -2: (right heavy) if balance(node.right) > 0: node.right = rotateRight(node.right) return rotateLeft(node) if balance(node) == 2: (left heavy) if balance(node.left) < 0: node.left = rotateLeft(node.left) return rotateRight(node) return node Two things I kept forgetting: update the lower node's height before the new root's, and always return the new subtree root so the parent pointer gets reassigned on the way back up the recursion.