DETAILED LR ROTATION IN AVL TREE – STEP-BY-STEP WITH DIAGRAMS

(The most confusing rotation – but after this, you’ll draw it in your sleep!)

When does LR Rotation happen?

LR = Left-Right Case
→ Imbalance at node X
→ Balance Factor of X = +2 (left-heavy)
→ But left child Y is right-heavy (BF of Y < 0)

This is the only case that needs DOUBLE ROTATION

BEST EXAM-GRADE EXAMPLE (Draw exactly this!)

Initial AVL Tree (Perfectly Balanced)

               50
             /    \
           30      70
          /  \       \
        20    40      80
             /  \
           35    45

Heights: 20(0), 35(0), 45(0), 40(1), 30(2), 80(0), 70(1), 50(3) → Valid

Now Delete Node 80 → Triggers LR Rotation!

After deleting 80:

               50
             /    \
           30      70          ← 70 now leaf → height 0
          /  \
        20    40
             /  \
           35    45

Now update heights bottom-up:

• 40 → left=35(h=0), right=45(h=0) → height = 1
• 30 → left=20(h=0), right=40(h=1) → height = 2, BF = 0–1 = -1 (right heavy!)
• 50 → left=30(h=2), right=70(h=0) → height = 3, BF = 2–0 = +2 → VIOLATION!

Imbalance at node 50 (X = 50)
Left child 30 (Y = 30) has BF = -1 → LR Case!

STEP-BY-STEP LR ROTATION (Draw this sequence – 15 marks guaranteed)

Before Any Rotation

               50  (X)            ← BF = +2 → Violation
             /    \
           30 (Y)   70
          /  \         BF of Y = -1 → Right heavy!
        20    40 (Z)
             /  \
           35    45

Step 1: LEFT ROTATION on Y (30)

→ Rotate left around node 30

After left rotation on 30:

               50
             /    \
           40      70
          /  \       \
        30    45      ?
       /  \
     20   35

Now 40 becomes left child of 50
30 becomes left child of 40
45 becomes right child of 40

Step 2: RIGHT ROTATION on X (50)

→ Now rotate right around node 50

After right rotation on 50:

               40  ← New Root!
             /    \
           30      50
          /  \       \
        20   35      70
              \
              45

FINAL BALANCED AVL TREE

               40
             /    \
           30      50
          /  \       \
        20   35      70
              \
              45

All heights:
- 20,35,45,70 → height 0
- 30 → height 1
- 50 → height 1
- 40 → height 2 → Perfectly balanced!

SUMMARY DIAGRAM TO DRAW IN EXAM (3 Stages)

Before LR:           After Left Rotate on 30:       After Right Rotate on 50:
       50                    50                            40
      /  \                  /  \                          /  \
    30    70              40    70                      30    50
   /  \                  /  \      \                    /  \     \
 20   40               30   45      ?                 20   35    70
     /  \             /  \                           /  \
   35    45         20   35                        45

ONE-LINE MEMORY TRICK (Write in exam)

"LR Case → First Left on child, then Right on parent → New root is the middle node (Z)"

FULL LR ROTATION FORMULA (Draw this box)

When X is left-heavy (BF=+2) but Y is right-heavy (BF<0):
1. Left rotate on Y (the left child of X)
2. Right rotate on X
→ Z (middle node) becomes new root of subtree

MOST ASKED EXAM QUESTION (15 Marks)

Q: Perform deletion of node 10 from the following AVL tree and show balancing steps.

         60
       /    \
     40      80
    /  \       \
  30    50      90
   \     \
   35    55

Answer:
After deleting 10 → imbalance at 60 → LR case → double rotation → final root becomes 50

You can now explain and draw LR rotation in 3 minutes flat in any exam!

You are officially an AVL Tree Rotation Master!
Want RL Rotation detailed example next? Say “RL”!