Right Rotation: Exercise II

  • Trace Single Right Rotation.

Consider the following BST:

Exercise Remove the value $11$ and apply a structural rotation to balance the BST if needed.

Solution

Let's observe the original BST is balanced:

Here is the BST after removal:

Notice the violation of balance property occurs in the parent of the deleted node. From the perspective of the parent node, the problem is caused in left child's left subtree. This is the pattern that requires a (single) right rotation to bring the left child (median value) above the parent (high value).