AVL Tree Rotations Explained Step by Step (With All 4 Cases)

AVL rotations are one of those topics that make sense in a lecture and fall apart the moment you try to do one on paper. Which node do you rotate? Left or right? Why do some cases need two rotations?

This post walks through all four cases one insert at a time, with the balance factors written out, so you can see exactly why each rotation happens.

Why AVL trees rotate at all

A plain binary search tree (BST) can become a linked list. Insert 10, 20, 30, 40, 50 in order and every node hangs off the right of the previous one. Search becomes O(n) instead of O(log n).

An AVL tree prevents this by keeping every node balanced. After each insert or delete it checks the balance factor of each node on the path back up to the root:

balance factor = height(left subtree) − height(right subtree)

The rule is simple: every node's balance factor must be −1, 0 or +1. When a node hits +2 or −2, it's unbalanced, and a rotation fixes it.

Rotations only rearrange a few pointers, so each one is O(1). That's why AVL insert, delete and search all stay O(log n) in the worst case.

The two basic moves

Every AVL fix is built from two moves.

Right rotation (used when the tree leans left):

      z                y
     /               /   \
    y        →      x     z
   /
  x

Left rotation (used when the tree leans right):

  z                    y
   \                 /   \
    y        →      z     x
     \
      x

In both cases, the middle value y moves up and becomes the new root of that subtree. The BST order (left < parent < right) is preserved.

Case 1: Left-Left (LL) → one right rotation

Insert 30, 20, 10:

    30   (bf +2)  ← unbalanced
   /
  20     (bf +1)
 /
10

The node 30 has balance factor +2 (leans left), and its left child 20 also leans left (+1). Both lean the same way, so one right rotation at 30 fixes it:

    20
   /  \
  10   30

Case 2: Right-Right (RR) → one left rotation

Insert 10, 20, 30:

10       (bf −2)  ← unbalanced
  \
   20    (bf −1)
     \
      30

The mirror image of Case 1. 10 leans right (−2) and its right child leans right too (−1). One left rotation at 10:

    20
   /  \
  10   30

Case 3: Left-Right (LR) → left rotation, then right rotation

Insert 30, 10, 20:

    30   (bf +2)  ← unbalanced
   /
  10     (bf −1)
    \
     20

Here's where people get stuck. 30 leans left, but its left child 10 leans right. The signs disagree, so a single right rotation at 30 would just produce another unbalanced tree.

The fix is two steps:

1. Left rotation at 10 turns it into a Left-Left case:

      30
     /
    20
   /
  10

1. Right rotation at 30 finishes the job:

    20
   /  \
  10   30

Case 4: Right-Left (RL) → right rotation, then left rotation

Insert 10, 30, 20:

10       (bf −2)  ← unbalanced
  \
   30    (bf +1)
  /
 20

The mirror of Case 3. 10 leans right but its right child leans left. Right rotation at 30, then left rotation at 10:

    20
   /  \
  10   30

The cheat sheet

Unbalanced node	Child leans	Case	Fix
+2 (left heavy)	left (+1 or 0)	LL	Right rotation
−2 (right heavy)	right (−1 or 0)	RR	Left rotation
+2 (left heavy)	right (−1)	LR	Left rotate child, then right rotate node
−2 (right heavy)	left (+1)	RL	Right rotate child, then left rotate node

Shortcut: if the node and its child lean the same way, one rotation. If they lean opposite ways, two rotations.

The code

Here's the core of it in Python. Each node stores its height so balance factors are cheap to compute.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

def height(n):
    return n.height if n else 0

def balance(n):
    return height(n.left) - height(n.right) if n else 0

def update(n):
    n.height = 1 + max(height(n.left), height(n.right))

def rotate_right(z):
    y = z.left
    z.left = y.right
    y.right = z
    update(z)
    update(y)
    return y

def rotate_left(z):
    y = z.right
    z.right = y.left
    y.left = z
    update(z)
    update(y)
    return y

def insert(node, key):
    if not node:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

    update(node)
    bf = balance(node)

    if bf > 1 and key < node.left.key:      # LL
        return rotate_right(node)
    if bf < -1 and key > node.right.key:    # RR
        return rotate_left(node)
    if bf > 1 and key > node.left.key:      # LR
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if bf < -1 and key < node.right.key:    # RL
        node.right = rotate_right(node.right)
        return rotate_left(node)

    return node

Notice that rotate_right and rotate_left each change just two pointers and update two heights. That's the whole O(1) trick.

Watch it happen instead of drawing it

Static diagrams only get you so far. The moment it really clicks is when you watch the balance factors change after each insert and see the subtree swing into place.

I built a free visualizer for exactly this: AVL tree visualization on VizStep. Insert your own values and step forward or back through each operation. It calls out the balance factor that triggered a rebalance ("Balance factor at 30 is 2"), names the rotation case (LL, RR, LR or RL), and highlights the matching pseudocode line. It's free, with no sign-up.

Try these sequences to trigger each case:

• 30, 20, 10 → LL
• 10, 20, 30 → RR
• 30, 10, 20 → LR
• 10, 30, 20 → RL

If you want to see why AVL trees are worth the extra work, compare it with a plain BST on the same input: BST vs AVL Tree.

Key takeaways

• An AVL tree keeps every balance factor in {−1, 0, +1}.
• Same-direction lean (LL, RR) needs one rotation.
• Opposite-direction lean (LR, RL) needs two rotations, and the first one just converts it into the simple case.
• Each rotation is O(1), so insert, delete and search stay O(log n) in the worst case.

If this helped, drop a comment with the data structure you'd like broken down next. Red-black trees and heaps are on my list.