BST Rotation

This page is about binary search tree rotation.

Rotating BSTs is a useful way to balance them and is an important step in Red-Black Trees and AVL Trees.

Rotation Steps

Determine if parent and child have a left-child relationship or right-child relationship
For a LEFT-child relationship, perform a RIGHT rotation
For a RIGHT-child relationship, perform a LEFT rotation
During a right rotation, the parent becomes the child's new right child, and the child's old right child becomes the parent's new left child
During a left rotation, the parent becomes the child's new left child, and the child's old left child becomes the parent's new right child
If the old parent had a parent, make sure to update the references to have the new parent as the root of this subtree