Course contentsShow
← Computer Science
Lesson 537 of 2,87213. Balanced TreesFree lesson

Left-Right Double Rotation

Combine left then right rotations to resolve the Left-Right imbalance pattern.

Left-Right Double Rotation

What you'll learn: How to fix a Left-Right imbalance in an AVL tree by combining two rotations.


The Problem

Sometimes a simple single rotation isn't enough. Imagine your tree is left-heavy (left subtree is taller), but the extra height comes from the right child of the left subtree. This is the Left-Right case — the imbalance "zigzags" down.

A single right rotation won't fix this because the problem node isn't in a straight line from the root.


The Solution: Two-Step Fix

The Left-Right Double Rotation performs:

  1. Left rotation on the left child (straightening the zigzag into a straight left-left line)
  2. Right rotation on the original imbalanced node (fixing the now-straightened imbalance)

Analogy: Think of straightening a bent paperclip. You can't fix a zigzag bend with one twist — you first unbend the middle section, then straighten the whole thing.


When to Use It

You detect this pattern when:

  • The balance factor at a node is +2 (left-heavy)
  • The balance factor of its left child is -1 (right-heavy)

The child's right-heaviness creates the zigzag that requires two rotations.


Why It Works

The first rotation (left on the left child) converts the Left-Right case into a Left-Left case. Now the tree has a straight left spine. The second rotation (right on the root) then resolves this straightforward imbalance, restoring balance to the entire subtree.


Key Takeaway: The Left-Right Double Rotation fixes zigzag imbalances by first rotating left to straighten the path, then rotating right to restore balance — always apply rotations in sequence to handle complex imbalance patterns.