cf.completefrontend
TREES & TRIES · ADVANCED

AVL tree (self-balancing search tree)

A binary search tree that rotates nodes after each insert so the two sides of every node differ in height by at most one, keeping operations O(log n).

Time O(log n) per insertSpace O(log n)2 practice problemsStep-through picture

The idea

A plain binary search tree can become a long chain when values arrive in sorted order, and then a search walks through every node. An AVL tree, named after its inventors Adelson-Velsky and Landis, prevents that.

Every node stores its height: the number of nodes on the longest path from it down to a leaf. The balance of a node is the height of its left subtree minus the height of its right subtree. The AVL rule says the balance must stay -1, 0, or 1 at every node.

After an insert, heights change along the path back up to the root. If some node's balance becomes 2 or -2, a rotation fixes it. A rotation moves a child up into its parent's place and the parent down, while keeping the left-smaller, right-bigger order.

An everyday example

Rebalancing a hanging mobile

A hanging mobile tilts when one side gets heavier. You fix it by lifting the heavier arm's middle piece up to be the new top hook, so the old top hangs from it on the other side. The pieces stay in the same left-to-right order, but the mobile hangs level again. Sometimes the weight sits on the inner part of the arm, and you first turn that arm, then lift.

How the example maps to the code
In the exampleIn the code
How tall each side hangsheight(node.left) and height(node.right)
The mobile tilting too farbalance > 1 or balance < -1
Lifting a piece to be the new toprotateRight(node) or rotateLeft(node)
Turning the arm first when the weight is on its inner partnode.left = rotateLeft(node.left)

From the slow way to avl tree (self-balancing search tree)

  1. A plain search tree is fast only while it's short. Insert 10, 20, 30, 40, 50 in that order and every value goes right: a chain of height 5, and every search is linear. You don't control the order in which users add data, so you need a tree that fixes its own shape.
  2. Rebuilding the whole tree into perfect balance after each insert would cost O(n) every time. Instead, ask for a looser rule that's cheap to keep: at every node, the heights of the two subtrees differ by at most 1. That rule is enough to keep the height O(log n), and an insert can only break it on the nodes along its own path.
  3. To check the rule, each node stores its height. After a recursive insert returns, update the height on the way back up and compute balance = height(left) - height(right). The first node where it reaches 2 or -2 needs a fix.
  4. The fix is a rotation: lift a child into its parent's place and hand one subtree across. It keeps the sorted order but moves one level of height from the tall side to the short side. When the new value went into the inner side, two rotations are needed. A search tree that checks heights on the way up and rotates when they differ by 2 is an AVL tree.

How it works

  1. Insert val as in a normal BST, recursively: go left if val < node.val, otherwise right. An empty spot becomes a new node with height 1.
  2. On the way back up, update the node's height from its children's heights.
  3. Compute balance = height(node.left) - height(node.right).
  4. If balance > 1, the left side is too tall. If the new value went into the left child's right side, first rotate the left child left. Then rotate node right.
  5. If balance < -1, do the mirror image: maybe rotate the right child right, then rotate node left.
  6. Return the node that now sits at the top of this subtree, so the parent links to it.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function height(node) {
  2. return node === null ? 0 : node.height;
  3. }
  4. function update(node) {
  5. node.height = 1 + Math.max(height(node.left), height(node.right));
  6. }
  7. function rotateRight(top) {
  8. const pivot = top.left;
  9. top.left = pivot.right;
  10. pivot.right = top;
  11. update(top);
  12. update(pivot);
  13. return pivot;
  14. }
  15. function rotateLeft(top) {
  16. const pivot = top.right;
  17. top.right = pivot.left;
  18. pivot.left = top;
  19. update(top);
  20. update(pivot);
  21. return pivot;
  22. }
  23. function avlInsert(node, val) {
  24. if (node === null) return { val, left: null, right: null, height: 1 };
  25. if (val < node.val) node.left = avlInsert(node.left, val);
  26. else node.right = avlInsert(node.right, val);
  27. update(node);
  28. const balance = height(node.left) - height(node.right);
  29. if (balance > 1) {
  30. if (val >= node.left.val) node.left = rotateLeft(node.left);
  31. return rotateRight(node);
  32. }
  33. if (balance < -1) {
  34. if (val < node.right.val) node.right = rotateRight(node.right);
  35. return rotateLeft(node);
  36. }
  37. return node;
  38. }

How fast it is

TimeO(log n) per insert
Extra memoryO(log n)

The balance rule keeps the height under about 1.44 log n. The insert walks one path down and back up, and each rotation is a few pointer changes. The recursion uses one call per level.

  • Best caseO(log n)

    Even the luckiest insert walks a path of about log₂ n nodes, because the tree is always balanced: there are no short paths to the bottom.

  • Average caseO(log n)

    Random inserts: a path of about log₂ n nodes, with a rotation on some of the inserts.

  • Worst caseO(log n)

    Sorted inserts like 1, 2, 3, ..., n, the input that ruins a plain search tree. Rotations keep the height small: inserting 1,000,000 sorted values gives a tree of height 20.

Common mistakes

  • Forgetting to update heights after a rotation, or updating the new top before the old top. Heights must be fixed from the bottom up.
  • Not using the returned node: writing avlInsert(node.left, val) instead of node.left = avlInsert(node.left, val). The rotations are then lost.
  • Doing a single rotation in the left-right or right-left case. The tree stays unbalanced in the other direction.
  • Deciding the case by the child's balance but sending equal values to a different side than the insert did. Use the same rule for duplicates everywhere.

When to use it

Look for these clues in a problem:

  • Values are inserted in an unknown order (maybe sorted) and searches must stay O(log n).
  • The problem asks you to keep a search tree balanced after each insert.
  • You need an ordered set or map with fast insert, search, and ordered walks.
  • The question talks about rotations or height-balanced trees.

Check yourself

Answer each one in your head first, then open it.

Why does the double rotation case exist?

When the new value is in the inner subtree, a single rotation moves that subtree to the other side without making it shorter, so the tree is still unbalanced. Rotating the child first moves the tall part to the outer side, where one more rotation fixes it.

In the trace, why did inserting 80 rotate at 60 and not at 40?

Heights are checked from the bottom up, and 60 was the first node with balance -2. After its rotation, that subtree was back to height 2, so 40 stayed at -1.

What is the fewest nodes an AVL tree of height 5 can have?

12. From N(h) = N(h - 1) + N(h - 2) + 1, the sequence is 1, 2, 4, 7, 12.

Why does update(top) run before update(pivot) in a rotation?

After the rotation, top is a child of pivot, and pivot's height depends on top's new height, so the child must be fixed first.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The property every operation keeps: the tree is a valid search tree, every node's stored height is correct, and every node's balance is -1, 0, or 1. A rotation only relinks three pointers among parts whose order is pivot, then the moved subtree, then top (for a right rotation), so the inorder order doesn't change and the search-tree rule survives.

An insert adds one leaf, so heights can grow by at most 1, and only along the path back to the root. Walking back up, update fixes each height. The first node with balance 2 or -2 is fixed by the matching rotation case, which brings that subtree back to the height it had before the insert. So no node above it sees any change, and at most one fix, a single or a double rotation, happens per insert.

The height stays small because of the rule. Let N(h) be the fewest nodes an AVL tree of height h can have. Its subtrees must have heights h - 1 and h - 2, so N(h) = N(h - 1) + N(h - 2) + 1, giving 1, 2, 4, 7, 12, 20, and so on. That grows exponentially, so n nodes force a height of at most about 1.44 log₂ n, and every operation, which walks one path, is O(log n).

Going deeper

3 more ideas

What a rotation does

rotateRight(top) takes pivot = top.left and lifts it up. top becomes the right child of pivot, and pivot's old right subtree (values between pivot and top) moves to be top's new left subtree. Every value keeps its place in sorted order, but the left side loses one level of height and the right side gains one.

Why the height stays about log n

With the balance rule, the smallest AVL tree of height h has its two subtrees of heights h - 1 and h - 2, much like Fibonacci numbers. These sizes grow exponentially, so a tree with n nodes has height at most about 1.44 log n. So search, insert, and delete are O(log n) in the worst case.

Four cases, two rotations

Left-left (the new value is in the left child's left side): one right rotation. Right-right: one left rotation. Left-right: rotate the left child left, then the node right. Right-left: rotate the right child right, then the node left. At most one of these happens per insert, because after it the subtree has the same height it had before the insert.

Work it by hand

Every step in a table, with why

Insert 6 values one at a time. One insert needs a single rotation and a later one needs a double rotation.

values = [40, 25, 60, 70, 80, 65], each inserted with `root = avlInsert(root, val)`

StepInsertNodeheightbalanceActionWhy
140-1-new rootThe first value becomes the whole tree, a node with height: 1.
2254021ok25 goes left. Back at 40, the left height is 1 and the right is 0, so the balance is 1, which is allowed.
3604020ok60 goes right, and 40 is perfectly balanced.
47060, then 402, then 3-1, then -1ok70 goes right of 60. Both nodes on the path lean right by one, which is still allowed.
580702-1ok80 goes right of 70. The first node checked on the way up is fine.
680603-2rotateLeft(60)60 has an empty left side and a right side of height 2. 80 is not less than 70, so the new value is on the outer side: the right-right case. One left rotation lifts 70 above 60.
780403-1okBack at 40, its right subtree is now 70 with children 60 and 80, height 2. The tree is [40, 25, 70, null, null, 60, 80].
865602-1ok65 goes right at 40, left at 70, and right at 60.
9657031ok70 leans left by one, which is allowed.
1065404-2rotateRight(70)40 has left height 1 and right height 3. 65 < 70, so the new value is on the inner side: the right-left case. First rotate the right child 70 to the right, which lifts 60 above it.
116540--rotateLeft(40)Then rotate 40 to the left, which lifts 60 to the root. 65 moves across to become 70's left child.

The final tree is [60, 40, 70, 25, null, 65, 80] with height 3. A plain search tree with the same inserts would have height 4. Two of the six inserts needed a fix: one single rotation and one double rotation.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
AVL tree (self-balancing search tree)O(log n)O(log n)Many searches mixed with inserts, and you need a guaranteed bound even on sorted input.
Plain binary search treeO(n)O(1)Values arrive in random order, and simple code matters more than a guarantee.
Sorted arrayO(n)O(1)Mostly reads with rare inserts: search is O(log n), but each insert shifts items.
Red-black treeO(log n)O(log n)Inserts and deletes are much more common than searches, so fewer rotations matter more than a slightly shorter tree.

Extra memory: O(log n) extra for the recursion, one call per level of the path. Each node also stores its height, a small fixed cost per node.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for AVL tree (self-balancing search tree) and the other approaches, on a scale where each line up is 10 times more steps.
  • AVL tree (self-balancing search tree), Red-black tree O(log n)
  • Plain binary search tree, Sorted array O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
AVL tree (self-balancing search tree)31020
Plain binary search tree101,0001 million
Sorted array101,0001 million
Red-black tree31020

Inputs that need care

5 tricky inputs
Inserting into an empty tree
Line 24 returns a new node with height: 1. The caller must store the returned root, as with every insert, because a rotation can change it.
Sorted input: 10, 20, 30
After 30, node 10 has balance -2, and 30 is not less than 20, so a single rotateLeft(10) makes 20 the root with children 10 and 30.
Duplicates
Equal values go right, through the else branch. The case tests val >= node.left.val and val < node.right.val match that rule, so a duplicate on the inner side still triggers the double rotation.
Calling avlInsert(root, val) without root = ...
When the root rotates, the new top is lost. In the trace, the root changes from 40 to 60 on the last insert.
A node with only one child
height(null) returns 0, so the balance is computed correctly. Reading node.left.height directly would throw on a missing child.

Variations and follow-ups

Twists interviewers add

Delete

Remove the value as in a plain search tree, then walk back up updating heights and fixing balances. Unlike insert, a fix can leave the subtree shorter, so more fixes may be needed higher up, at most one per level, still O(log n).

Red-black trees

A looser rule, no path more than twice as long as another, means fewer rotations on insert and delete but a slightly taller tree, up to about 2 log₂ n. Many standard library sorted maps use them.

Order statistics

Store each node's subtree size and update it next to height. Then "the k-th smallest value" and "how many values are below x" take O(log n) by comparing k with the left subtree's size.

Treaps and skip lists

They balance with randomness instead of strict rules: each node gets a random priority, or each item a random number of levels. The expected height is O(log n), and the code is often shorter.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it when a question needs a sorted structure with fast inserts and a worst-case guarantee: "keep a running median", "count smaller numbers after each one", or "design a sorted set".
  • You rarely write a full AVL tree in an interview. Explain the balance rule, draw one rotation, and name the four cases; that usually covers what's asked.
  • Draw the left-right case by hand with 30, 10, 20 and show why one rotation isn't enough: rotating 30 right alone makes 10 the root with 30 and 20 below it, still unbalanced, now leaning the other way.
  • Expect "why at most one fix per insert?". Because the fixed subtree goes back to the height it had before the insert, so every ancestor sees no change.

Where frontend code uses it

The same idea in real UI code
  • VS Code's text buffer, the piece tree, keeps its pieces in a balanced binary search tree (a red-black tree, a close relative of the AVL tree), so jumping to any line stays fast in huge files.
  • Ordered collections in libraries, used for things like sorted timelines or price ladders in trading dashboards, rely on balanced trees to keep inserts and lookups O(log n).

Related algorithms