In the Binary Search Tree chapter, you saw that a BST is fast only when it is balanced. If we insert values in sorted order, something bad happens:
Insert 10, 20, 30, 40, 50 into a normal BST:
10
\
20
\
30
\
40
\
50The "tree" has become a linked list. Searching for 50 now takes 5 comparisons instead of about 3, and with n values every operation becomes O(n).
What if the tree could fix its own shape every time it became lopsided? That is exactly what an AVL Tree does. With the same five values, an AVL tree looks like this:
20
/ \
10 40
/ \
30 50Same values, same sorted order, but a much smaller height.
What is an AVL Tree?
An AVL tree is a self-balancing Binary Search Tree in which, for every node, the heights of the left and right subtrees differ by at most 1. After each insertion or deletion, the tree restores this property using rotations.
It is named after its inventors, G. M. Adelson-Velsky and E. M. Landis, who described it in 1962. It was the first self-balancing BST ever invented.
An AVL tree is still a BST, so everything you learned about BSTs still applies:
Left Subtree < Node < Right Subtree
Inorder traversal gives sorted orderThe only addition is the balance rule.
Height and Balance Factor
As mentioned in the Trees chapter, height can be counted in edges or in nodes. In this chapter's code we count nodes, which is the usual choice for AVL implementations:
height(null) = 0
height(leaf) = 1
height(node) = 1 + max(height(left), height(right))The balance factor of a node is:
balance factor = height(left subtree) - height(right subtree)(The difference is the same whichever height convention you use.)
In an AVL tree, every node must have a balance factor of -1, 0 or +1.
Balance factor | Meaning |
|---|---|
| Left side is one level taller (fine) |
| Both sides are equal (fine) |
| Right side is one level taller (fine) |
| Too left-heavy, needs fixing |
| Too right-heavy, needs fixing |
Example with balance factors written next to each node:
Balanced (valid AVL): Not balanced:
30 (+1) 30 (+2)
/ \ /
20 (+1) 40 (0) 20 (+1)
/ /
10 (0) 10 (0)In the right tree, node 30 has a left subtree of height 2 and a right subtree of height 0, so its balance factor is +2. It must be fixed.
Rotations: How an AVL Tree Fixes Itself
A rotation is a small, local rearrangement of a few nodes that changes the shape of the tree while keeping the BST order intact. It only changes a couple of pointers, so it takes O(1) time.
There are two basic rotations: right rotation and left rotation. Combining them gives the four cases we need.
Right Rotation
Used when a node is left-heavy. Its left child x moves up, and the node y moves down to the right.
y x
/ \ / \
x T3 rotate T1 y
/ \ right → / \
T1 T2 T2 T3Here T1, T2 and T3 are whole subtrees (possibly empty). Notice what happens to T2: it was the right child of x, and it becomes the left child of y. That is the only "tricky" pointer change.
Why is the BST order still correct? Before and after the rotation, the inorder sequence is the same:
T1 < x < T2 < y < T3static Node rotateRight(Node y) {
Node x = y.left;
Node t2 = x.right;
// Perform rotation
x.right = y;
y.left = t2;
// Update heights: y first (it is now below x)
updateHeight(y);
updateHeight(x);
return x; // new root of this subtree
}Left Rotation
The mirror image, used when a node is right-heavy:
x y
/ \ / \
T1 y rotate x T3
/ \ left → / \
T2 T3 T1 T2static Node rotateLeft(Node x) {
Node y = x.right;
Node t2 = y.left;
// Perform rotation
y.left = x;
x.right = t2;
updateHeight(x);
updateHeight(y);
return y;
}The order of the height updates matters: the node that moved down must be updated first, because the new top node's height depends on it.
The Four Imbalance Cases
When a node becomes unbalanced, we look at which side is heavy and then at which side of that child is heavy. This gives four cases, named by the path from the unbalanced node towards the heavy part.
1. Left-Left (LL) Case → One Right Rotation
Insert 30, 20, 10:
30 (+2) 20
/ / \
20 (+1) rotate 10 30
/ right(30) →
10Node 30 is left-heavy, and its left child 20 is also left-heavy (or balanced). A single right rotation at 30 fixes it.
2. Right-Right (RR) Case → One Left Rotation
Insert 10, 20, 30:
10 (-2) 20
\ / \
20 (-1) rotate 10 30
\ left(10) →
303. Left-Right (LR) Case → Left Rotation, Then Right Rotation
Insert 30, 10, 20:
30 (+2) 30 20
/ / / \
10 (-1) left(10) 20 right(30) 10 30
\ → / →
20 10Node 30 is left-heavy, but its left child 10 is right-heavy. A single right rotation at 30 would not work: it would just create a mirror-image problem. So we first rotate the child left to turn it into an LL case, then rotate right.
4. Right-Left (RL) Case → Right Rotation, Then Left Rotation
Insert 10, 30, 20:
10 (-2) 10 20
\ \ / \
30 (+1) right(30) 20 left(10) 10 30
/ → \ →
20 30Here is the summary:
Case | Node balance | Child balance | Fix |
|---|---|---|---|
LL |
| left child | Right rotate the node |
LR |
| left child | Left rotate the left child, then right rotate the node |
RR |
| right child | Left rotate the node |
RL |
| right child | Right rotate the right child, then left rotate the node |
The child balance of exactly 0 never happens right after an insertion, but it can happen after a deletion. In that case the single rotation (LL or RR) is the correct choice.
AVL Insertion
Insertion is a normal BST insertion followed by a "repair on the way back up":
Insert the value exactly like in a BST (recursively).
As the recursion returns to each ancestor, update that ancestor's height.
Compute its balance factor. If it is
+2or-2, apply the correct rotation.
First, the node and helper methods. The only change from the BST node is the extra height field:
class Node {
int data;
int height;
Node left;
Node right;
Node(int data) {
this.data = data;
this.height = 1; // a new node is a leaf
}
}static int height(Node node) {
return node == null ? 0 : node.height;
}
static int balanceFactor(Node node) {
return node == null ? 0 : height(node.left) - height(node.right);
}
static void updateHeight(Node node) {
node.height = 1 + Math.max(height(node.left), height(node.right));
}We put the four cases into one rebalance() method, so that both insertion and deletion can use it:
static Node rebalance(Node node) {
updateHeight(node);
int balance = balanceFactor(node);
// Left heavy
if (balance > 1) {
// Left-Right case: first rotate the left child left
if (balanceFactor(node.left) < 0) {
node.left = rotateLeft(node.left);
}
// Left-Left case
return rotateRight(node);
}
// Right heavy
if (balance < -1) {
// Right-Left case: first rotate the right child right
if (balanceFactor(node.right) > 0) {
node.right = rotateRight(node.right);
}
// Right-Right case
return rotateLeft(node);
}
return node; // already balanced
}Now insertion looks almost exactly like BST insertion, except for the last line:
static Node insert(Node root, int value) {
// 1. Normal BST insertion
if (root == null) {
return new Node(value);
}
if (value < root.data) {
root.left = insert(root.left, value);
}
else if (value > root.data) {
root.right = insert(root.right, value);
}
else {
return root; // duplicates are ignored
}
// 2. Update height and fix any imbalance on the way back up
return rebalance(root);
}Because a rotation can change the root of a subtree, every recursive call returns the (possibly new) root, and the parent stores it with root.left = ... or root.right = .... The caller must also do root = insert(root, value).
Step-by-Step Example
Let's insert 10, 20, 30, 40, 50, 25 one by one.
Insert 10, 20, 30. After inserting 30, node 10 has balance -2 and its right child has balance -1: an RR case. Left rotate at 10:
10 20
\ / \
20 → 10 30
\
30Insert 40. It goes to the right of 30. Balance of 30 is -1, balance of 20 is -1. Still valid, no rotation.
20
/ \
10 30
\
40Insert 50. Now node 30 has balance -2 (its right child 40 has balance -1): an RR case at 30. Left rotate at 30:
20 20
/ \ / \
10 30 → 10 40
\ / \
40 30 50
\
50Notice that the rotation happened at 30, the lowest unbalanced ancestor, and after fixing it the whole tree was balanced again.
Insert 25. Path: 25 > 20 → go right to 40, 25 < 40 → go left to 30, 25 < 30 → becomes left child of 30.
20 (-2)
/ \
10 40 (+1)
/ \
30 50
/
25Node 20 now has balance -2, and its right child 40 has balance +1. This is the RL case. First right rotate at 40, then left rotate at 20:
20 30
/ \ / \
10 30 → 20 40
/ \ / \ \
25 40 10 25 50
\
50Final tree: root 30, height 3. Its preorder is 30 20 10 25 40 50, which the program below confirms.
AVL Deletion
Deletion follows the same pattern:
Delete the node exactly like in a BST (the three cases: leaf, one child, two children using the inorder successor).
On the way back up, call
rebalance()on every ancestor.
static Node delete(Node root, int value) {
// 1. Normal BST deletion
if (root == null) {
return null;
}
if (value < root.data) {
root.left = delete(root.left, value);
}
else if (value > root.data) {
root.right = delete(root.right, value);
}
else {
if (root.left == null) {
return root.right;
}
if (root.right == null) {
return root.left;
}
Node successor = findMin(root.right);
root.data = successor.data;
root.right = delete(root.right, successor.data);
}
// 2. Rebalance on the way back up
return rebalance(root);
}One important difference from insertion: after an insertion, at most one rotation (single or double) is needed to fix the whole tree. After a deletion, fixing one node can make an ancestor unbalanced, so rotations may be needed at several levels, up to O(log n) of them. Since we call rebalance() on every ancestor anyway, the code handles this automatically.
Example: starting from the final tree above, delete 10, 20 and 25:
Delete 10: Delete 20: Delete 25: Rebalance (RR at 30):
30 30 30 (-2) 40
/ \ / \ \ / \
20 40 25 40 40 30 50
\ \ \ \
25 50 50 50A Complete Java Example
The program below builds the AVL tree from the step-by-step example, searches it, deletes a few values, and finally inserts 1 to 1000 in sorted order to show how small the height stays.
class Node {
int data;
int height;
Node left;
Node right;
Node(int data) {
this.data = data;
this.height = 1; // a new node is a leaf
}
}
class Main {
static int height(Node node) {
return node == null ? 0 : node.height;
}
static int balanceFactor(Node node) {
return node == null ? 0 : height(node.left) - height(node.right);
}
static void updateHeight(Node node) {
node.height = 1 + Math.max(height(node.left), height(node.right));
}
static Node rotateRight(Node y) {
Node x = y.left;
Node t2 = x.right;
// Perform rotation
x.right = y;
y.left = t2;
// Update heights: y first (it is now below x)
updateHeight(y);
updateHeight(x);
return x; // new root of this subtree
}
static Node rotateLeft(Node x) {
Node y = x.right;
Node t2 = y.left;
// Perform rotation
y.left = x;
x.right = t2;
updateHeight(x);
updateHeight(y);
return y;
}
static Node rebalance(Node node) {
updateHeight(node);
int balance = balanceFactor(node);
// Left heavy
if (balance > 1) {
// Left-Right case: first rotate the left child left
if (balanceFactor(node.left) < 0) {
node.left = rotateLeft(node.left);
}
// Left-Left case
return rotateRight(node);
}
// Right heavy
if (balance < -1) {
// Right-Left case: first rotate the right child right
if (balanceFactor(node.right) > 0) {
node.right = rotateRight(node.right);
}
// Right-Right case
return rotateLeft(node);
}
return node; // already balanced
}
static Node insert(Node root, int value) {
// 1. Normal BST insertion
if (root == null) {
return new Node(value);
}
if (value < root.data) {
root.left = insert(root.left, value);
}
else if (value > root.data) {
root.right = insert(root.right, value);
}
else {
return root; // duplicates are ignored
}
// 2. Update height and fix any imbalance on the way back up
return rebalance(root);
}
static Node findMin(Node root) {
while (root.left != null) {
root = root.left;
}
return root;
}
static Node delete(Node root, int value) {
// 1. Normal BST deletion
if (root == null) {
return null;
}
if (value < root.data) {
root.left = delete(root.left, value);
}
else if (value > root.data) {
root.right = delete(root.right, value);
}
else {
if (root.left == null) {
return root.right;
}
if (root.right == null) {
return root.left;
}
Node successor = findMin(root.right);
root.data = successor.data;
root.right = delete(root.right, successor.data);
}
// 2. Rebalance on the way back up
return rebalance(root);
}
static boolean search(Node root, int value) {
while (root != null) {
if (value == root.data) {
return true;
}
root = value < root.data ? root.left : root.right;
}
return false;
}
static void preorder(Node root) {
if (root == null) {
return;
}
System.out.print(root.data + " ");
preorder(root.left);
preorder(root.right);
}
static void inorder(Node root) {
if (root == null) {
return;
}
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
public static void main(String[] args) {
Node root = null;
int[] values = {10, 20, 30, 40, 50, 25};
for (int v : values) {
root = insert(root, v);
}
System.out.print("Preorder: ");
preorder(root);
System.out.print("\nInorder: ");
inorder(root);
System.out.println("\nRoot: " + root.data);
System.out.println("Height: " + height(root));
System.out.println("Search 25: " + search(root, 25));
System.out.println("Search 35: " + search(root, 35));
root = delete(root, 10);
root = delete(root, 20);
root = delete(root, 25);
System.out.print("After deleting 10, 20, 25: ");
preorder(root);
System.out.println("\nRoot: " + root.data);
System.out.println("Height: " + height(root));
// Inserting 1..1000 in sorted order
Node big = null;
for (int i = 1; i <= 1000; i++) {
big = insert(big, i);
}
System.out.println("Height after inserting 1 to 1000: " + height(big));
}
}Output:
Preorder: 30 20 10 25 40 50
Inorder: 10 20 25 30 40 50
Root: 30
Height: 3
Search 25: true
Search 35: false
After deleting 10, 20, 25: 40 30 50
Root: 40
Height: 2
Height after inserting 1 to 1000: 10A normal BST built from 1 to 1000 in sorted order would have height 1000. The AVL tree has height 10, which is the smallest possible height for 1000 nodes (210 - 1 = 1023 is the most nodes a binary tree of height 10 can hold).
Time and Space Complexity
An AVL tree with n nodes always has height O(log n). More precisely, its height is less than about 1.44 × log2(n + 2), so it is never more than about 44% taller than a perfectly balanced tree.
Operation | Normal BST (worst case) | AVL Tree (worst case) |
|---|---|---|
Search |
|
|
Insert |
|
|
Delete |
|
|
Find min / max |
|
|
Inorder traversal |
|
|
Why? Each operation walks one path from the root to a leaf (O(log n) nodes), and at each node it does O(1) work: a comparison, a height update and possibly a rotation.
Space: O(n) for the nodes (each node stores one extra integer for its height), plus O(log n) for the recursion stack.
AVL Tree vs Red-Black Tree
The other famous self-balancing BST is the Red-Black Tree. It uses node colours and a looser balance rule instead of exact heights.
AVL Tree | Red-Black Tree | |
|---|---|---|
Balance rule | Strict: heights differ by at most 1 | Looser: longest path is at most twice the shortest |
Height | About | About |
Search speed | Slightly faster (shorter tree) | Slightly slower |
Insert / delete | More rotations, especially on delete | Fewer rotations |
Best for | Read-heavy workloads (many lookups) | Write-heavy workloads (many updates) |
Used in | Lookup-heavy in-memory data, teaching and interviews | Java |
In Java, you rarely write your own balanced tree. When you need a sorted map or set with O(log n) operations, use TreeMap or TreeSet, which are implemented as Red-Black Trees. But understanding AVL trees is the best way to learn how balancing works, and AVL rotations are a common interview topic.
Common Mistakes
1. Forgetting to Update Heights
Every time the structure changes, the heights of the affected nodes must be recalculated. A stale height gives a wrong balance factor and leads to wrong (or missing) rotations.
2. Updating Heights in the Wrong Order After a Rotation
Update the node that moved down first, then the node that moved up. The new parent's height depends on its children.
3. Not Using the Returned Root
Rotations change which node is at the top of a subtree. Writing insert(root, 5); instead of root = insert(root, 5); loses the new root.
4. Mixing Up LR and RL
Look at the balance of the child. If the node is left-heavy but its left child is right-heavy, it is LR: rotate the child left first. A single rotation in a zig-zag case does not fix anything.
5. Losing the Middle Subtree (T2)
During a rotation, the inner subtree T2 must be re-attached to the node that moved down. Forgetting the line y.left = t2; (or x.right = t2;) silently deletes part of the tree.
Interview Tips
Be able to draw all four rotation cases from memory, with
T1,T2,T3subtrees.Know the definition:
|height(left) - height(right)| ≤ 1for every node, not just the root.A common question: "Insert these values into an AVL tree and draw the final tree." Practise with sequences like
1, 2, 3, 4, 5, 6, 7(the result is a perfect tree with root4).Related coding problems: Balanced Binary Tree (check if a tree satisfies the AVL height condition), Convert Sorted Array to Binary Search Tree (build a height-balanced BST), and Balance a Binary Search Tree.
Know why
TreeMapgivesO(log n)guarantees whileHashMapgivesO(1)average but no ordering.
The Main Idea
An AVL tree is a Binary Search Tree that keeps itself balanced. For every node:
balance factor = height(left) - height(right) ∈ {-1, 0, +1}When an insertion or deletion breaks this rule, it is fixed with rotations:
LL → right rotation
RR → left rotation
LR → left rotation on child, then right rotation
RL → right rotation on child, then left rotationBecause the height always stays O(log n):
Search → O(log n)
Insert → O(log n)
Delete → O(log n)An AVL tree gives you all the benefits of a Binary Search Tree, with a guarantee that it will never degrade into a linked list.