Skip to content

level 6 · Trees

AVL Tree

A search tree that refuses to become a list — it rotates itself level again.

13 min 105 XP

what is it

Start here

The Binary Search Tree lesson ended on a warning: insert sorted values and the tree stretches into a straight line. Height n instead of log n. Search collapses from 20 steps to a million. All that elegant structure, gone — and sorted input isn't even unusual.

An AVL tree is the fix, and it's the first self-balancing tree ever invented (1962). It keeps one promise: at every node, the left and right sides differ in height by at most 1. That number — left height minus right height — is the **balance factor**, and the moment it hits ±2, the tree has tipped over.

The repair is a **rotation**: lift a child up, let the parent sink down. The astonishing thing is that a rotation *cannot* break the search-tree ordering. Everything smaller is still on the left, everything bigger still on the right. It re-shapes the tree while leaving its meaning untouched, which is exactly why you're allowed to do it whenever you like.

The visualization feeds it sorted values on purpose. A plain BST would build a ladder. Watch this one refuse — rotating every couple of inserts, and staying stubbornly, provably short.

The cost: a little bookkeeping on every insert, and up to O(log n) rotations. What you buy is a guarantee — O(log n) search, forever, no matter what order the data arrives in. Databases and filesystems are built on that guarantee.

real-life analogy

Picture it

A mobile hanging over a cot

Hang too many shapes on one arm and the whole mobile tips. So you don't add a counterweight or prop it up — you re-hang it around a different point, and the same shapes now balance. Nothing was added or removed; you changed which piece is on top.

interactive visualization

Watch it run

Deliberately sorted — a plain BST would build a straight line. Watch this one rotate.

A plain search tree fed sorted values becomes a straight line, and search degrades to O(n). An AVL tree watches its own balance and rotates itself level again. The default input here is sorted on purpose — so you can watch it refuse to become a list.

step 01/15

  • comparing
  • moving
  • in the output
  • target · placed
  • on the path
1function insert(node, value) {
2 if (node === null) return new Node(value);
3
4 if (value < node.value) node.left = insert(node.left, value);
5 else node.right = insert(node.right, value);
6
7 update(node); // recompute height
8 return rebalance(node); // fix it if it tipped over
9}
10
11function rebalance(node) {
12 const bf = height(node.left) - height(node.right);
13
14 if (bf > 1) { // too heavy on the LEFT
15 if (height(node.left.left) < height(node.left.right))
16 node.left = rotateLeft(node.left); // left-right case
17 return rotateRight(node);
18 }
19 if (bf < -1) { // too heavy on the RIGHT
20 if (height(node.right.right) < height(node.right.left))
21 node.right = rotateRight(node.right); // right-left case
22 return rotateLeft(node);
23 }
24 return node; // balanced enough
25}

variables right now

Nothing in play yet — press play.

comparisons 0moves 0

the dry run · every step, in words

15 steps

complexity

What it costs

best case
O(log n)
average
O(log n)
worst case
O(log n)
extra memory
O(n)

O(log n) search, insert and delete — GUARANTEED, in the worst case. That's the whole point: a plain BST is O(log n) only if you're lucky with the input order. AVL removes the luck, at the cost of a few rotations.

  • O(1)
  • O(log n) · this one
  • O(n)
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Forgetting to update heights on the way back up the recursion.

    The balance factor is computed from heights. Stale heights mean the tree thinks it's balanced when it isn't, and it silently stops rebalancing.

  • Missing the left-right and right-left cases.

    If the heavy child leans the *other* way, a single rotation doesn't fix it — you must rotate the child first. Skip this and one rotation just tips the tree the other way.

  • Worrying that rotating breaks the search order.

    It can't. A rotation is carefully designed so smaller stays left and bigger stays right. That's precisely why it's a legal move.

  • Using AVL when you write far more than you read.

    AVL keeps the tree very strictly balanced, which means more rotations. A red-black tree balances more loosely — slightly slower reads, noticeably cheaper writes.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+105 XP

01What is a node's balance factor?

02Does a rotation break the binary-search-tree ordering?

03You insert 10, 20, 30, 40, 50 in order. What does a plain BST do, and what does an AVL do?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.