Right Rotation: Exercise III
- Trace Single Right Rotation.
Consider the following BST:

Exercise Insert the value 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 to be the parent of , the latter needs to go to the right of . However, is already to the right of . So we need to attach to the left of (where used to be).
