AVL Tree Visualization for Coding Interviews
LL / RR / LR / RL rotations animated on rebalance.
Concept
An AVL tree is a binary search tree that maintains an extra invariant: at every node, the heights of the two children differ by at most one. That tight height bound forces the tree to stay within roughly 1.44 log2(n) levels, which in turn guarantees that search, insert, and delete all run in O(log n) worst-case, not just on average. AVL was the first self-balancing BST, proposed in 1962 by Adelson-Velsky and Landis, and it remains the textbook example of how a handful of local rotations can preserve a global height property. Compared to red-black trees, AVL trees are more strictly balanced (shorter in practice), which makes lookups marginally faster, but they rebalance more eagerly on insert and delete, which makes updates slightly more expensive. Production databases and language runtimes usually pick red-black for that reason; AVL is the right pick when reads dominate writes and worst-case lookup latency matters.
How it works
Every node stores a height field that equals 1 + max(height(left), height(right)), with null children treated as height 0. After every insert or delete, you walk back up the path from the modified leaf to the root, recompute each ancestor's height, and check the balance factor, defined as height(left) - height(right). If the balance factor is within [-1, 0, 1] the node is fine; otherwise one of four rotation cases applies. Left-Left: an insertion in the left subtree of the left child - one right rotation fixes it. Right-Right: symmetric - one left rotation. Left-Right: insertion in the right subtree of the left child - first left-rotate the left child, then right-rotate the node. Right-Left: symmetric - right-rotate the right child, then left-rotate the node. A rotation is a constant-time pointer rewiring that preserves the BST invariant and reduces subtree height by one. Because at most O(log n) ancestors can become unbalanced and each fix is O(1), total update cost stays O(log n). Delete uses the same rotation cases, but you may need to rebalance multiple ancestors on the way up because deletion can reduce height by more than one level.
Implementation
public class AVLTree {
static class AVLNode {
int key, height;
AVLNode left, right;
AVLNode(int key) { this.key = key; this.height = 1; }
}
private AVLNode root;
private int height(AVLNode n) { return n == null ? 0 : n.height; }
private int balanceFactor(AVLNode n) { return n == null ? 0 : height(n.left) - height(n.right); }
private void updateHeight(AVLNode n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }
private AVLNode rightRotate(AVLNode y) {
AVLNode x = y.left, t2 = x.right;
x.right = y; y.left = t2;
updateHeight(y); updateHeight(x);
return x;
}
private AVLNode leftRotate(AVLNode x) {
AVLNode y = x.right, t2 = y.left;
y.left = x; x.right = t2;
updateHeight(x); updateHeight(y);
return y;
}
public void insert(int key) { root = insert(root, key); }
private AVLNode insert(AVLNode node, int key) {
if (node == null) return new AVLNode(key);
if (key < node.key) node.left = insert(node.left, key);
else if (key > node.key) node.right = insert(node.right, key);
else return node;
updateHeight(node);
int bf = balanceFactor(node);
// Left-Left
if (bf > 1 && key < node.left.key) return rightRotate(node);
// Right-Right
if (bf < -1 && key > node.right.key) return leftRotate(node);
// Left-Right
if (bf > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right-Left
if (bf < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
public boolean contains(int key) {
AVLNode n = root;
while (n != null) {
if (key == n.key) return true;
n = key < n.key ? n.left : n.right;
}
return false;
}
}Complexity
- Search:
O(log n) - Insert:
O(log n) - Delete:
O(log n) - Space:
O(n)
Common pitfalls
- Forgetting to update the height field after rotations - every balance decision afterward becomes wrong.
- Computing the balance factor from stale child heights because you updated the parent before the children.
- Picking the wrong rotation case: LR and RL need two rotations, not one.
- Skipping rebalance after delete - delete can violate the invariant just as much as insert, and needs the same four-case check.
- Treating null children as height -1 in some code paths and 0 in others; pick a convention and use it everywhere.
Key design decisions & trade-offs
- AVL vs red-black — Chosen: AVL when reads dominate. AVL keeps the tree strictly shorter, so lookups are slightly faster; red-black accepts a looser bound in exchange for cheaper updates.
- Height storage — Chosen: Store full height, not balance factor. Height makes rotations uniform and debugging easier; balance-factor-only implementations save a byte per node but complicate recomputation.
- Iterative vs recursive insert — Chosen: Recursive with rebalance on unwind. Recursion lets each ancestor rebalance itself as the call stack unwinds, avoiding an explicit parent-pointer walk.
Practice problems
Interview follow-ups
- Implement AVL delete with the four rotation cases on the way up.
- Augment every node with a subtree-size field to support order statistics.
- Compare AVL insert performance against red-black under a random workload.
- Persist the AVL tree to disk using a B-tree instead when node count exceeds memory.
- Support bulk-loading a sorted input in O(n) without rebalancing by building bottom-up.
Why it matters
AVL Tree is a core part of the Trees toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".