Right Rotation: Exercise III

  • Trace Single Right Rotation.

Consider the following BST:

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