You learn binary search trees and walk away believing every operation is O(log n). It isn't. That guarantee only holds when the tree stays balanced, and a plain BST has no mechanism to enforce that. Insert [1, 2, 3, 4, 5] into an empty BST and you've built a linked list with extra steps.

TL;DR: An AVL tree adds one rule to a BST. No node's left and right subtrees can differ in height by more than 1. When an insertion breaks the rule, the tree fixes itself through rotations. Every operation stays O(log n). The four rotation cases aren't four separate things to memorise. They're two atomic moves combined twice.

The balance rule everything else hangs on

An AVL tree is a self balancing BST where, for every node, the heights of its left and right subtrees differ by at most 1. That's the whole rule. Every operation that preserves the rule preserves O(log n).

You track the rule with the balance factor:

balance_factor(node) = height(left_subtree) - height(right_subtree)

A node is balanced when its balance factor is -1, 0, or +1. Zero means both subtrees have the same height. +1 means the left is one level taller. -1 means the right is. When an insertion or deletion pushes any node's balance factor to -2 or +2, the tree is unbalanced and needs fixing.

The fix is always a rotation, and it's always local. You don't rebuild the tree. You rearrange 2 or 3 pointers near the imbalance and the invariant snaps back into place.

This single rule is strict enough to guarantee logarithmic height. An AVL tree with n nodes has height at most about 1.44 log(n). Slightly taller than a perfectly balanced tree, but the difference is a constant factor. Every operation traverses from root to leaf, so when height stays logarithmic, so does runtime.

Why the rule matters more than it looks

A plain BST gives you none of this. Insert the values [1, 2, 3, 4, 5] into an empty BST. Each value is larger than the last, so every insertion goes right. The resulting tree is a straight line, structurally identical to a linked list. Searching for 5 walks all five nodes. O(n), not O(log n).

Sorted input isn't unusual either. Database indices built from timestamped logs, primary keys assigned by an auto-increment column, sensor readings ordered by time. All of these produce sorted insertion sequences. A plain BST degenerates into a linked list on every one of them.

Performance depends entirely on height. Balanced, you get O(log n). Degenerate, you get O(n). Lose control of the height, lose control of the performance. That's the whole reason self balancing exists.

The four rotation cases, and why they're really just two

Every AVL imbalance falls into one of four cases. Each one is resolved by a specific rotation that preserves the BST ordering (left < parent < right) while restoring the height balance.

There are only two atomic moves: a left rotation and a right rotation. The four cases are these two moves applied once or twice.

• LL case (left child of a left-heavy node): single right rotation on the unbalanced node
• RR case (right child of a right-heavy node): single left rotation on the unbalanced node
• LR case (right child of a left-heavy node): left rotate the left child first to straighten the kink, then right rotate the unbalanced node
• RL case (left child of a right-heavy node): right rotate the right child first, then left rotate the unbalanced node

The single rotations handle the "outside" imbalances. The double rotations handle the "inside" imbalances where a single rotation would just move the heavy side from one position to another without fixing it. The trick is recognising which side of the parent is heavy AND which side of that child is heavy. Those two answers pick the case.

def right_rotate(z):
    y = z.left
    T3 = y.right
    y.right = z
    z.left = T3
    z.height = 1 + max(height(z.left), height(z.right))
    y.height = 1 + max(height(y.left), height(y.right))
    return y

Notice what the rotation actually does. It moves 3 pointers and updates 2 heights. That's it. Constant time. The O(log n) part of an insertion comes from walking down the tree to find the insertion point and walking back up to check balance factors. The rotation itself is free by comparison.

Tracing an insertion sequence

Walk through inserting [3, 2, 1, 4, 5] into an empty AVL tree. I find that watching two different rotations fire in the same sequence is what makes the four-case table click.

Inserting 3 creates a single-node tree with balance factor 0.

Inserting 2 sends it left of 3. Node 3's balance factor is +1 (left subtree height 1, right subtree height 0). Still within the rule.

Inserting 1 triggers the first rotation. 1 goes left of node 2. Walking back up, node 2's balance factor is +1 and node 3's is +2. That's an LL case (node 3 is left-heavy, its left child 2 is also left-heavy). A right rotation on node 3 puts node 2 at the root, node 1 on the left, and node 3 on the right. All balance factors drop to 0.

Inserting 4 goes right from node 2 to node 3, then right again to become node 3's right child. Walking back, node 3's balance factor is -1, node 2's is 0. Within the rule.

Inserting 5 breaks balance again. It lands as node 4's right child. Walking back up, node 4's balance factor is -1, but node 3's hits -2. That's an RR case. A left rotation on node 3 moves node 4 into node 3's position, with node 3 as 4's left child and node 5 as 4's right child. All balance factors back to 0.

Final tree: node 2 at the root, node 1 on the left, node 4 on the right, with 3 and 5 as 4's children. Height is 2.

A plain BST with the same insertion order [3, 2, 1, 4, 5] wouldn't degenerate this badly. But try [1, 2, 3, 4, 5] and the plain BST becomes a linked list of height 4. The AVL version still has height 2.

The full insertion algorithm bundles the BST insert with the balance check on the way back up:

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)

    node.height = 1 + max(height(node.left), height(node.right))
    bf = balance_factor(node)

    if bf > 1 and key < node.left.key:
        return right_rotate(node)
    if bf < -1 and key > node.right.key:
        return left_rotate(node)
    if bf > 1 and key > node.left.key:
        node.left = left_rotate(node.left)
        return right_rotate(node)
    if bf < -1 and key < node.right.key:
        node.right = right_rotate(node.right)
        return left_rotate(node)

    return node

After every insertion you only check balance factors along the path from the inserted node back to the root. At most one rotation (single or double) is needed.

Why deletion is harder than insertion

This is the part most beginner tutorials gloss over and the part interviewers like to probe.

Insertion can break balance at one node along the ancestor path. You rotate once and you're done. Deletion isn't that clean.

When you remove a node, the height reduction can propagate upward. Fixing the first imbalanced ancestor might shorten that subtree, which then unbalances the next ancestor up. In the worst case you'll rotate at every level from the deleted node's position back to the root. That's O(log n) rotations instead of the single rotation insertion needs.

The rotation selection logic stays the same. You still compute balance_factor(node) and check whether the imbalance is LL, RR, LR, or RL. The difference is that you can't stop after the first fix. You have to keep walking up.

There's also a subtlety with the node you're actually removing. If the target has two children, you replace it with its in-order successor (smallest in the right subtree) or its in-order predecessor (largest in the left subtree), then delete that node instead. The replacement is identical to plain BST deletion. The AVL-specific work starts afterward, during the upward balance check.

I'd argue most interview questions won't ask you to implement AVL deletion from scratch. But understanding why deletion is more expensive than insertion is what separates "I've memorised the four cases" from "I've actually thought about the invariant." If an interviewer asks about the tradeoff of stricter balance, deletion cost is the concrete answer.

When to reach for AVL vs Red-Black

In interviews, AVL trees show up two ways: explaining self balancing BSTs conceptually, and implementing balanced insertion from scratch. Red-Black trees show up as a "why don't standard libraries use AVL" question.

Plain BST. Fine when input is random or the problem doesn't require worst-case guarantees. Tree problems on LeetCode typically assume balanced input and don't ask you to maintain balance yourself.

Red-Black tree. Relaxes the balance constraint to height up to 2 log(n) in exchange for cheaper insertion and deletion. At most 2 rotations per operation, vs potentially O(log n) for AVL deletion. Java's TreeMap, C++'s std::map, and Linux's CFS process scheduler all use Red-Black trees. So does the Linux kernel's anonymous VMA tree. Most standard libraries do.

AVL tree. Enforces stricter balance. Maximum height about 1.44 log(n) versus about 2 log(n) for Red-Black. Lookups are faster because the tree is shorter. The tradeoff is that insertions and deletions are slower because AVL trees may need more rotations to maintain the stricter rule.

Why are AVL trees less common in production despite being older and simpler? Looser balance makes insertion-heavy workloads faster, and most real systems insert and delete more than they search-only.

For interviews though, AVL trees are the better answer. The rotation logic is more intuitive than Red-Black's five-case colour rules. If an interviewer asks you to implement a self balancing BST from scratch, AVL is the cleaner choice under time pressure. I keep seeing candidates wedge themselves into Red-Black trees and run out of time at the recolouring step. AVL trees let you spend that same time tracing the four cases instead.

Honest credit where it's due: Red-Black trees aren't "worse." They're optimised for a different workload. The standard library authors knew exactly what they were trading. It's the same engineering call you'd make if you were building a key-value store that inserts billions of times a day. AVL is the wrong choice there. It's only the right choice for read-heavy workloads, or for an interview where the simpler invariant lets you finish before the timer.

The three mistakes that cost candidates in interviews

These are the patterns I keep seeing on AVL questions, in roughly the order they show up.

• Stale heights after rotation. You rotate nodes y and z but forget to recalculate their height fields. The next balance factor check uses stale data and every decision downstream is wrong from that point on.
• Top-down balance checking. You insert at a leaf and trace upward to find the first unbalanced ancestor. Starting from the root downward misses the actual imbalance point or applies a rotation at the wrong node.
• Misidentified LR / RL cases. Under pressure it's tempting to see a left-heavy node and immediately right rotate. If the left child is right-heavy, a single right rotation makes things worse. Sketching the three nodes on paper before choosing the rotation takes five seconds and avoids a cascading error that's painful to debug mid-interview.

Codeintuition's Binary Search Tree course walks the balance invariant from first principles. If the four-case table still feels like four separate things to memorise, the BST course traces balance factor computation across multiple tree shapes before any rotation code appears.

I wrote a longer version on my blog that walks deletion with the upward rebalance loop and includes the AVL vs Red-Black tradeoff matrix.

Which AVL rotation case took the longest to internalise for you, and what was the problem or sketch that finally made it click?