What Is an AVL Tree? The Self-Balancing BST That Stays O(log n)

A regular binary search tree makes a promise it can't always keep. Insert sorted data and it degenerates into a linked list. Your O(log n) lookup becomes O(n). The AVL tree exists to hold that promise no matter what you throw at it.

Georgy Adelson-Velsky and Evgenii Landis invented it in 1962, the first self-balancing BST. Every operation runs in O(log n), and unlike some data structures where that's an average-case claim, AVL trees guarantee it as a worst case. No asterisks.

The Problem a Plain BST Can't Solve

Start with a binary search tree and insert 1, 2, 3, 4, 5 in order. You get this:

Technically still a BST. Every left child is smaller, every right child is larger. But searching for 5 touches every node. That's O(n), not O(log n). The tree is a list wearing a tree costume.

Nothing enforces balance during insertions. A BST places nodes wherever the invariant allows. If your input happens to be sorted, you get a degenerate tree. Which, in practice, happens constantly, because people sort things before storing them. Classic.

The Balance Factor: AVL's Core Invariant

An AVL tree adds one rule on top of the BST invariant: at every node, the heights of the left and right subtrees can differ by at most 1.

That difference is the balance factor:

balance_factor = height(left_subtree) - height(right_subtree)

Valid values are -1, 0, or +1. Anything outside that range means the tree has gone out of balance and needs fixing. Think of it as the AVL tree's own internal anxiety meter. Goes past ±1 and it starts rotating things until it feels better.

Height is the number of edges on the longest path from a node down to a leaf. A null child has height -1 by convention.

This single constraint is what keeps tree height at O(log n). Specifically, an AVL tree with n nodes has height at most 1.44 log₂(n). Even in the worst case, it's logarithmic.

A Concrete Example: Watch a Rotation Happen

Insert 1, 2, 3 into an AVL tree.

After inserting 1 and 2:

1       balance factors:
 \      1: -1 (right height 1, left height -1)
  2     2: 0

Still balanced. Insert 3:

1           balance factors:
 \          1: -2  ← VIOLATION
  2         2: -1
   \        3: 0
    3

Node 1 now has a balance factor of -2. The tree is right-heavy. To fix it, we perform a left rotation at node 1.

Pull node 2 up to where 1 was. Node 1 becomes 2's left child:

  2         balance factors:
 / \        2: 0
1   3       1: 0, 3: 0

Balanced. And still a valid BST: 1 < 2 < 3. The tree basically did a little yoga pose to fix its posture.

The Four Rotation Cases

There are four patterns that trigger rebalancing. Each has a corresponding fix.

Diagram of all four AVL rotation cases: LL, RR, LR, and RL, showing before and after node positions

Case	Shape	Fix
Left-Left (LL)	New node in left subtree of left child	Single right rotation
Right-Right (RR)	New node in right subtree of right child	Single left rotation
Left-Right (LR)	New node in right subtree of left child	Left rotate child, then right rotate root
Right-Left (RL)	New node in left subtree of right child	Right rotate child, then left rotate root

LL and RR cases need one rotation. LR and RL are zigzag patterns that need two. The zigzag cases are why AVL tree implementations have a reputation for being annoying to get right. You do a rotation to straighten out the zigzag, then another rotation to actually fix the balance. It is the data structure equivalent of parallel parking.

Here is the left rotation in Python:

def rotate_left(z):
    y = z.right
    T2 = y.left

    y.left = z
    z.right = T2

    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))

    return y

Right rotation is the mirror. After every insertion or deletion, you walk back up the path to the root, update heights, check balance factors, and rotate wherever needed.

A minimal insert showing the full cycle:

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

    node.height = 1 + max(get_height(node.left), get_height(node.right))
    balance = get_balance(node)

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

    return node

Each insertion triggers at most O(log n) rotation checks walking up the tree, but each rotation is O(1). Insertion stays O(log n) total.

AVL Tree Time and Space Complexity

Operation	Time Complexity
Search	O(log n)
Insert	O(log n)
Delete	O(log n)
Space	O(n)

These are all worst-case bounds, not average-case. That is the whole point. AVL trees cap height at 1.44 log₂(n), so no matter what order data arrives, operations never slip past logarithmic.

Compare that to a plain BST: O(log n) average but O(n) worst case. The distinction matters in production when you have no control over input order. You have no control over input order. Users do chaotic things.

AVL Trees in the Real World

You have almost certainly used an AVL tree without knowing it.

Java's TreeMap and TreeSet use a red-black tree, a close cousin that trades lookup speed for faster insertions. Databases and in-memory index structures often prefer AVL trees because the stricter balance makes lookups faster in read-heavy workloads.

AVL trees rotate more frequently on insertions and deletions to maintain the tighter balance factor. Red-black trees allow wider imbalance, so they rotate less and writes are cheaper. Read-heavy workload: AVL wins. Writes dominate: red-black is typically better. The full comparison is worth reading if you need to choose.

The standard library almost never exposes AVL trees directly. In Java you use TreeMap. In Python you reach for sortedcontainers.SortedList. In C++ you use std::map and std::set, which are typically red-black under the hood. Knowing the internals helps you reason about performance even when you're not writing the tree yourself.

How AVL Trees Show Up in Interviews

You will rarely be asked to implement a full AVL tree from scratch. It is long, fiddly, and mostly tests whether you remember four rotation cases, not whether you can solve problems.

Interviewer: "We'd like to see you invert and merge two unsorted binary trees." Candidate: "Does that come up a lot in this job role?"

The eternal question. The answer is always "sometimes."

What does come up:

"What is an AVL tree and why does it exist?" (system design conversations, design-your-own-database questions)
"What is the time complexity of operations on a self-balancing BST?" (O(log n) worst case)
"When would you use a BST over a hash map?" (ordered traversal, range queries, predecessor/successor)
Implementing height tracking on a BST node, or identifying when a BST is unbalanced

The key insight to land: the balance factor invariant is what guarantees O(log n) worst case, and rotations are the mechanism that restores the invariant without breaking BST ordering. Those are two separate ideas. Explaining both clearly signals real understanding.

For ordered-data problems, a self-balancing BST gives you things a hash map cannot: sorted iteration, floor and ceiling queries, and efficient rank/select operations. The BST vs hash map comparison covers when to reach for each one.

If you want to practice articulating this under pressure, SpaceComplexity runs voice-based mock interviews where you explain your reasoning out loud, which is exactly where most candidates trip on conceptual questions like this.