Right Rotation: Exercise III

  • Trace Single Right Rotation.

Consider the following BST:

Exercise Insert the value $3$ 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 great-grandparent of the inserted node. From the perspective of the great-grandparent node, the problem is caused in left child's left subtree. This is the pattern that requires a (single) right rotation. However, this case is a bit tricky:

When you bring $7$ to be the parent of $14$, the latter needs to go to the right of $7$. However, $11$ is already to the right of $7$. So we need to attach $11$ to the left of $14$ (where $7$ used to be).