Right Rotation: Exercise I

  • Trace Single Right Rotation.

Consider the following BST:

Exercise Insert the value $4$ 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 insertion:

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