AVL Tree Deletion Steps

AVL TREE DELETION – FULL DETAILED STEP-BY-STEP

(With Exact Diagrams You Can Draw in Exam – 15–20 Marks Guaranteed!)

AVL Tree Properties Recap (Write First in Exam)
- Binary Search Tree
- Balance Factor (BF) of every node = |height(left) – height(right)| ≤ 1
- After deletion → restore balance using 4 rotations: LL, RR, LR, RL

DELETION PROCESS (Standard Steps – Always Write This)

Perform normal BST deletion
Leaf → delete
One child → replace with child
Two children → replace with Inorder Successor (right subtree’s minimum)
Update heights bottom-up
At every node on the path back to root, check Balance Factor
If |BF| = 2 → Violation → fix with one of 4 rotations

FULL EXAMPLE (Most Asked in Exams)

Initial Balanced AVL Tree

                    50
                  /    \
               30        70
              /  \      /  \
            20    40  60    80
           /            \     \
         10             65    90

Heights: 10(0), 20(1), 65(0), 90(0), 60(1), 80(1), 40(0), 30(2), 70(2), 50(3) → Valid AVL

CASE-BY-CASE DELETION

Delete 10 (Leaf) → Easy

Just remove 10
Update heights → 20 becomes height 0 → 30 becomes height 1 → 50 height 2
→ Still balanced!

Delete 65 (Leaf under 60)

Remove 65 → 60 now height 0
70: left=60(h=0), right=80(h=1) → BF = 0–1 = -1 → OK
→ No rotation needed

Delete 90 (Leaf under 80) → Triggers Rotation!

                    50
                  /    \
               30        70
              /  \      /  \
            20    40  60    80   ← 80 had right child 90 → now leaf
           /                     (height becomes 0)
         10

Now update heights:
- 80 → height 0
- 70 → left(60)=0, right(80)=0 → height 1
- 50 → left(30)=1, right(70)=1 → height 2 → balanced

Still OK!

Delete 80 → NOW REAL IMBALANCE!

Step 1: 80 has no children → delete directly
Step 2: Update height of 70 → now only left child 60 → height = 1
Step 3: Go up to 50

                    50
                  /    \
               30        70       ← now height 1
              /  \      /
            20    40  60
           /
         10

Balance Factors:
- 50: left height=2 (30), right height=1 (70) → BF = 2–1 = +1 → OK
Wait — no imbalance?

Let’s do a harder standard example that triggers all 4 rotations.

BEST EXAM EXAMPLE (Triggers All 4 Rotations)

Initial AVL Tree

                    30
                  /    \
                20      40
               /         \
             10           50
                         /  \
                       45   60

We delete nodes one by one to show LL, RR, LR, RL rotations.

1. Delete 10 → Triggers RR Rotation (Right-Right)

After deleting 10:

Now at node 30:
left height = 1 (20), right height = 3 (50) → BF = 1–3 = -2 → Violation!
Look at right child (40): BF = -1 → RR case

Fix: Left Rotate on 30

After RR Rotation (Left Rotate):

                    40
                  /    \
                30      50
               /       /  \
             20      45   60

Now balanced!

2. Delete 60 → Triggers LL Rotation (Left-Left)

After deleting 60:

At node 40: left=2, right=1 → BF = +1 → OK
At node 50: left=1, right=0 → BF = +1 → OK
→ No rotation

Let’s delete 20 instead → real LL

New Tree:

Delete 50 → 45 becomes child of 40
Then delete 45 → now:

                    40
                  /    \
                30      NIL
               /
             20
           /
         15
       /
     10

Heights: 40 → left=3, right=0 → BF = +3 → Violation
Left child 30 → BF = +2 → LL case

Fix: Right Rotate on 40

After LL Rotation:

Balanced!

3. LR Rotation Example (Left-Right)

Tree:

Delete 30 → 40 moves up → imbalance at 50
50: left=3 (40), right=0 → BF=+3
Left child 40: BF = 0–1 = -1 → LR case

Fix: Left rotate on 30 (now 40’s left), then Right rotate on 50

Final:

4. RL Rotation Example

Symmetric to LR – just mirror

4 ROTATIONS SUMMARY (DRAW THIS TABLE IN EXAM – 10 MARKS!)

Imbalance	Child BF	Case	Rotation Sequence
BF = +2	≥ 0	LL	Right Rotate on X
BF = +2	< 0	LR	Left on child → Right on X
BF = -2	≤ 0	RR	Left Rotate on X
BF = -2	> 0	RL	Right on child → Left on X

DIAGRAMS TO DRAW IN EXAM

LL Rotation             RR Rotation
    X                         X
   / \                       / \
  A   Y                     Y   C
     / \                   / \
    B   C                 A   B
  → Right Rotate →       → Left Rotate →
    Y                         Y
   / \                       / \
  X   C                     A   X
 / \                           / \
A   B                         B   C

LR Rotation                     RL Rotation
    X                               X
   / \                             / \
  A   Y                           Y   C
     / \                         / \
    Z   C                       A   Z
   / \                             / \
  B   C                           B   C

MOST ASKED EXAM QUESTION (15 Marks)

Q: Delete node 10 from the following AVL tree and show step-by-step balancing.

        30
       /  \
     20    40
    /        \
  10          50
             /
           45

Answer:
1. Delete 10 → 20 becomes leaf
2. Height of 30: left=1, right=2 → BF = -1 → OK? Wait, recalculate
3. Actually imbalance at root → RR case → Left rotate → final tree with 40 as root

You can now solve ANY AVL Deletion question in exam!

Pro Tip: In exam, always write:
- “Deletion same as BST”
- “Update heights bottom-up”
- “Check BF on path to root”
- “4 possible rotations based on child’s BF”

You are now AVL Tree Deletion Master!
Next? Say “B-TREE” or “SPLAY TREE”!

Last updated: Nov 28, 2025