Left Rotation: Exercise V
- Trace Single Left Rotation.
Consider the following BST:
Exercise Start from the leaf (6) and visit the parent nodes back to the root. As soon as you see an imbalanced node, apply rotation to fix it.
Solution
Let's note the heights and balance factors in the original BST:
We can perform a left rotation to bring $4$ to the left of $5$:
We then perform another left rotation to bring $3$ to the left of $5$:
