Balanced Trees and AVL Basics
A balanced tree is a binary search tree that keeps its height as close as possible to the theoretical minimum for the number of nodes it holds, so no branch ever grows dramatically longer than any other. An AVL tree, named after its inventors Adelson-Velsky and Landis, is the classic self-balancing binary search tree: it tracks a “balance factor” at every node and performs local rotations whenever an insertion or deletion tips that factor too far, guaranteeing O(log n) height at all times. This matters because a plain BST’s performance depends entirely on the shape it happens to end up in — insert already-sorted data into one and it degenerates into a straight chain, turning every O(log n) operation into O(n). AVL trees fix that by rebalancing themselves after every change, so search, insert, and delete stay fast no matter what order the data arrives in.
Overview: How Balanced Trees Work
Start with the problem a plain binary search tree has. A BST only guarantees that every node’s left subtree holds smaller keys and its right subtree holds larger keys — it makes no promise about shape. Insert the keys 1, 2, 3, 4, 5, 6, 7 in that order into an ordinary BST and every new key is larger than everything already in the tree, so each one becomes the right child of the previous node. The result is a straight chain seven nodes long: not really a tree at all, but a linked list wearing a tree’s clothing. Searching for 7 now costs O(n) comparisons instead of the O(log n) a tree is supposed to deliver, because the height of the tree equals the number of nodes instead of roughly log2(n).
A balanced tree prevents this by actively enforcing a shape constraint after every modification. AVL trees do it with a simple rule: at every node, compute the balance factor — the height of the left subtree minus the height of the right subtree. In a valid AVL tree, every node’s balance factor is -1, 0, or +1. The moment an insertion (or deletion) pushes some node’s balance factor to +2 or -2, that node is “unbalanced,” and the algorithm repairs it immediately, before the operation is considered finished, using one of four rotation patterns.
The Four Rotation Cases
A rotation is a local restructuring of two or three nodes that fixes the height imbalance while preserving the BST ordering property — an in-order traversal of the tree gives the exact same sorted sequence before and after a rotation. Each rotation is O(1): it only reassigns a handful of pointers, it never touches nodes outside the small neighborhood being rotated. There are four cases, named after the direction of the “heavy” side and where the newly inserted key landed:
- Left-Left (LL): the left subtree is heavy, and the new key went into the left subtree’s left side. Fixed with a single right rotation.
- Right-Right (RR): the mirror image of LL — fixed with a single left rotation.
- Left-Right (LR): the left subtree is heavy, but the new key went into the left subtree’s right side, forming a zigzag. A single rotation can’t fix a zigzag, so this case needs two: first rotate the left child left, turning it into an LL shape, then rotate the node itself right.
- Right-Left (RL): the mirror image of LR — rotate the right child right, then rotate the node itself left.
Insertion works exactly like a normal recursive BST insert on the way down, but on the way back up (as the recursive calls return), each ancestor node recomputes its stored height and checks its balance factor. Because a single insertion can only ever create an imbalance of exactly one of these four shapes at the lowest unbalanced ancestor, and each shape is repaired in O(1), at most one rotation (single or double) is ever needed per insertion — the tree is fully rebalanced after fixing that one ancestor, so the whole insert stays O(log n).
Time and Space Complexity
Unlike a plain BST, an AVL tree’s complexity does not depend on the order keys arrive in — the balance invariant guarantees the same bound in the best, average, and worst case for every operation.
| Operation | Plain BST (worst case) | AVL Tree (guaranteed) |
|---|---|---|
| Search | O(n) |
O(log n) |
| Insert | O(n) |
O(log n) |
| Delete | O(n) |
O(log n) |
| Space | O(n) |
O(n) |
The O(log n) bound isn’t just a hopeful label — it follows from the balance-factor rule. Because every node’s left and right subtree heights differ by at most one, an AVL tree of height h is forced to contain at least a Fibonacci-like number of nodes: the minimum-node AVL tree of height h has one more node than the minimum-node tree of height h - 1 plus the minimum-node tree of height h - 2. Since Fibonacci numbers grow exponentially, inverting that relationship shows the height h can grow only logarithmically with the node count n — specifically h stays below roughly 1.44 * log2(n). That constant factor is why AVL trees are described as “more rigidly balanced” than looser structures like Red-Black trees. Space is O(n) to store n nodes (each with a key, two child pointers, and a small integer height), plus O(log n) auxiliary space on the call stack during a recursive search, insert, or delete, since the recursion depth never exceeds the tree’s height.
Examples
Example 1: Why a Plain BST Can Go Wrong
This example inserts the keys 1 through 7 in ascending order into an ordinary (non-balancing) BST and measures the resulting height, to see the worst case concretely before looking at how AVL trees avoid it.
class BSTNode:
def __init__(self, key: int) -> None:
self.key = key
self.left: "BSTNode | None" = None
self.right: "BSTNode | None" = None
def insert_bst(root: "BSTNode | None", key: int) -> "BSTNode":
if root is None:
return BSTNode(key)
if key < root.key:
root.left = insert_bst(root.left, key)
else:
root.right = insert_bst(root.right, key)
return root
def height(root: "BSTNode | None") -> int:
if root is None:
return 0
return 1 + max(height(root.left), height(root.right))
def main() -> None:
root: "BSTNode | None" = None
for key in [1, 2, 3, 4, 5, 6, 7]:
root = insert_bst(root, key)
print(f"Height of BST after inserting sorted 1..7: {height(root)}")
main()
Output:
Height of BST after inserting sorted 1..7: 7
Trace it by hand: 1 becomes the root. 2 is compared against 1, is not smaller, so it becomes 1‘s right child. 3 is compared against 1 (goes right), then against 2 (goes right again), becoming 2‘s right child. Every subsequent key repeats the pattern: always larger than the current node, always heading right. Seven nodes end up chained in a single line, so the height equals the node count instead of the roughly 3 a balanced tree of 7 nodes would have (log2(7) ≈ 2.8).
Example 2: Formalizing “Balanced” with a Checker Function
Before building a self-balancing tree, it helps to have a function that can check whether any given binary tree satisfies the height-balance property — this is also a common interview question in its own right. The function returns the subtree height while it recurses, but short-circuits to -1 the instant it finds an imbalance anywhere below, so it never wastes time computing heights for the rest of the tree once it already knows the answer is “no.”
class TreeNode:
def __init__(self, key: int) -> None:
self.key = key
self.left: "TreeNode | None" = None
self.right: "TreeNode | None" = None
def is_balanced(root: "TreeNode | None") -> bool:
def check(node: "TreeNode | None") -> int:
if node is None:
return 0
left_height = check(node.left)
if left_height == -1:
return -1
right_height = check(node.right)
if right_height == -1:
return -1
if abs(left_height - right_height) > 1:
return -1
return 1 + max(left_height, right_height)
return check(root) != -1
def main() -> None:
# Skewed tree: 1 -> 2 -> 3 -> 4, each node has only a right child
skewed = TreeNode(1)
skewed.right = TreeNode(2)
skewed.right.right = TreeNode(3)
skewed.right.right.right = TreeNode(4)
# Balanced tree: root 2 with children 1 and 3
balanced = TreeNode(2)
balanced.left = TreeNode(1)
balanced.right = TreeNode(3)
print(f"Skewed tree balanced? {is_balanced(skewed)}")
print(f"Balanced tree balanced? {is_balanced(balanced)}")
main()
Output:
Skewed tree balanced? False
Balanced tree balanced? True
For the skewed tree, check() reaches node 4 (a leaf), returning height 1. Back at node 3, the left height is 0 and the right height is 1 — still fine, difference of 1, returns height 2. Back at node 2, left height is 0 and right height is 2 — a difference of 2, which exceeds the allowed 1, so check() returns -1 right there. That -1 propagates all the way back up through node 1 without any further work, and is_balanced reports False. The three-node balanced tree, by contrast, has a left leaf and a right leaf of equal height under the root, so every difference is 0 and it reports True.
Example 3: A Full AVL Insert with Rotations
This is the complete algorithm: a recursive BST insert that, on the way back up, updates each node’s stored height, computes its balance factor, and applies the correct one of the four rotation cases whenever a node is found unbalanced. Inserting the same sorted keys 1 through 7 that produced a height-7 chain in Example 1 should now produce a tree of height 3.
class AVLNode:
def __init__(self, key: int) -> None:
self.key = key
self.left: "AVLNode | None" = None
self.right: "AVLNode | None" = None
self.height = 1
def get_height(node: "AVLNode | None") -> int:
return node.height if node else 0
def get_balance(node: "AVLNode | None") -> int:
if node is None:
return 0
return get_height(node.left) - get_height(node.right)
def update_height(node: "AVLNode") -> None:
node.height = 1 + max(get_height(node.left), get_height(node.right))
def rotate_right(y: "AVLNode") -> "AVLNode":
x = y.left
t2 = x.right
x.right = y
y.left = t2
update_height(y)
update_height(x)
return x
def rotate_left(x: "AVLNode") -> "AVLNode":
y = x.right
t2 = y.left
y.left = x
x.right = t2
update_height(x)
update_height(y)
return y
def insert_avl(node: "AVLNode | None", key: int) -> "AVLNode":
if node is None:
return AVLNode(key)
if key < node.key:
node.left = insert_avl(node.left, key)
else:
node.right = insert_avl(node.right, key)
update_height(node)
balance = get_balance(node)
if balance > 1 and key < node.left.key:
return rotate_right(node)
if balance < -1 and key >= node.right.key:
return rotate_left(node)
if balance > 1 and key >= node.left.key:
node.left = rotate_left(node.left)
return rotate_right(node)
if balance < -1 and key < node.right.key:
node.right = rotate_right(node.right)
return rotate_left(node)
return node
def inorder(node: "AVLNode | None", result: list[int]) -> None:
if node:
inorder(node.left, result)
result.append(node.key)
inorder(node.right, result)
def main() -> None:
root: "AVLNode | None" = None
for key in [1, 2, 3, 4, 5, 6, 7]:
root = insert_avl(root, key)
result: list[int] = []
inorder(root, result)
print(f"In-order traversal: {result}")
print(f"AVL tree height after inserting sorted 1..7: {get_height(root)}")
print(f"Root key: {root.key}, balance factor at root: {get_balance(root)}")
main()
Output:
In-order traversal: [1, 2, 3, 4, 5, 6, 7]
AVL tree height after inserting sorted 1..7: 3
Root key: 4, balance factor at root: 0
The in-order traversal still comes out perfectly sorted — proof that rotations never break the BST ordering property, they only reshape the tree. The height dropped from 7 (Example 1) to 3, and the tree settled into a perfectly balanced shape with 4 at the root, 2 and 6 as its children, and the remaining leaves 1, 3, 5, 7 underneath — the best possible arrangement for 7 nodes.
How It Works Step by Step
To see a rotation happen in isolation, trace just the first three insertions from Example 3: keys 1, 2, then 3, using the same insert_avl logic.
| Step | Action | Tree shape after the step | Balance factor at root |
|---|---|---|---|
| 1 | Insert 1 |
1 alone (a single node) |
0 |
| 2 | Insert 2 |
1 with right child 2 |
-1 (still within range, no rotation) |
| 3 | Insert 3 |
3 becomes 2‘s right child first, making 1‘s balance factor -2 |
-2 — unbalanced, an RR case |
| 4 | Rotate | rotate_left(1) runs: 2 becomes the new root, 1 becomes its left child, 3 stays its right child |
0 — balanced again |
Walking through step 4 in detail: rotate_left is called with x bound to node 1. It sets y = x.right, which is node 2. It saves t2 = y.left, which is None here (node 2 had no left child yet). It then rewires: y.left = x makes node 1 the left child of node 2, and x.right = t2 clears node 1‘s old right pointer (setting it to None, since t2 was None). Both heights are recomputed — node 1 is now a leaf with height 1, and node 2 has height 2 — and node 2 is returned as the new subtree root. The caller (the top-level loop) replaces its reference to the root with this returned node, and the tree is balanced again in constant time.
Common Mistakes
Mistake 1: Forgetting to Recompute Heights After a Rotation
The syntax checker that validates this course’s code only confirms your Python compiles — it can’t tell you that a height was never updated. This is the single most common AVL bug: a rotation reassigns the child pointers but the programmer forgets to call update_height on both nodes afterward, leaving stale height values that make every subsequent balance-factor calculation wrong.
def rotate_left_buggy(x: "AVLNode") -> "AVLNode":
y = x.right
t2 = y.left
y.left = x
x.right = t2
# BUG: heights of x and y are never recomputed here
return y
This compiles fine and even seems to “work” for a single rotation, because the rest of the code still reads x.height and y.height without erroring — it just gets stale, wrong numbers. A few insertions later, a balance factor computed from those stale heights can be off by one or two, causing the tree to either skip a rotation it needed or trigger one it didn’t. The fix is to always call update_height on both nodes involved in a rotation, in the correct order — the old parent x first (since it’s now lower in the tree and its subtrees are already final), then the new parent y (whose height depends on x‘s freshly updated height):
def rotate_left_fixed(x: "AVLNode") -> "AVLNode":
y = x.right
t2 = y.left
y.left = x
x.right = t2
update_height(x)
update_height(y)
return y
Mistake 2: Treating Every Imbalance as a Single-Rotation Case
It’s tempting to simplify the rebalancing logic to just two cases — “left-heavy, rotate right” and “right-heavy, rotate left” — but that only handles the LL and RR cases correctly. It silently fails on the LR and RL zigzag cases, where a single rotation leaves the tree just as unbalanced as before (only in the opposite direction).
def rebalance_buggy(node: "AVLNode", key: int, balance: int) -> "AVLNode":
if balance > 1:
return rotate_right(node)
if balance < -1:
return rotate_left(node)
return node
Consider inserting 3, then 1, then 2. After inserting 1, node 3 is left-heavy with balance factor 1 — no rotation needed yet. Inserting 2 makes it go right of 1, and now node 3‘s balance factor becomes 2: an LR case, because the new key 2 landed in 1‘s right subtree, not its left. Calling rotate_right(3) directly (as the buggy version does) just moves node 1 to the top without ever fixing the zigzag underneath it, so the resulting shape is still unbalanced. The correct version checks which side of the child the key landed on before choosing single vs. double rotation:
def rebalance_fixed(node: "AVLNode", key: int, balance: int) -> "AVLNode":
if balance > 1 and key < node.left.key:
return rotate_right(node)
if balance < -1 and key >= node.right.key:
return rotate_left(node)
if balance > 1 and key >= node.left.key:
node.left = rotate_left(node.left)
return rotate_right(node)
if balance < -1 and key < node.right.key:
node.right = rotate_right(node.right)
return rotate_left(node)
return node
Note also that is_balanced from Example 2 checks a stronger, more general property (any binary tree, computed from scratch by walking the whole tree) than an AVL tree’s own balance factor (a single node’s cached local check) — don’t confuse “this specific node’s children differ in height by at most 1” with “this entire tree satisfies the global height-balance property,” even though a correctly implemented AVL tree guarantees both are true everywhere, all the time.
Best Practices
- Always update a node’s stored height immediately after any pointer change and before reading its balance factor — reading balance factors from stale heights is the most common source of AVL bugs.
- Store height as an integer field on each node (as shown here) rather than recomputing it recursively on every balance check; recomputing from scratch turns an
O(log n)insert into anO(n log n)one. - When an imbalance is found, always compare the newly inserted key against the child’s key to pick the correct one of the four rotation cases (LL, RR, LR, RL) — never rotate based on the sign of the balance factor alone.
- Reach for an AVL tree specifically when you need a guaranteed
O(log n)worst case and searches vastly outnumber insertions and deletions — its stricter balance means faster lookups but more rotation overhead on writes. If insertions and deletions are frequent, a Red-Black tree (used internally by C++’sstd::mapand Java’sTreeMap) tolerates looser balance in exchange for fewer rotations per write. - For read-heavy workloads built once and rarely modified, consider simply sorting a Python list and using the
bisectmodule for binary search — it avoids the overhead of node objects and pointer-chasing entirely and is often faster in practice due to cache locality. - While developing a self-balancing tree, run a brute-force checker like
is_balancedfrom Example 2 after every insert to catch a broken rotation immediately, rather than discovering the bug much later from a subtle performance regression.
Practice Exercises
- Implement
delete_avl(node, key)for the AVL tree from Example 3. Deletion is trickier than insertion: after removing a node (handle the no-child, one-child, and two-child cases like a normal BST delete), you must walk back up and rebalance at every ancestor whose balance factor now exceeds1or-1— unlike insertion, a single deletion can require more than one rotation on the way back up. - Write
count_rotations(keys: list[int]) -> intthat inserts each key fromkeysinto a fresh AVL tree one at a time and returns the total number of rotations performed. Hint: add a counter thatrotate_leftandrotate_righteach increment by one before returning. - Interview-style: given a Python list that is already sorted in ascending order, write
build_balanced_bst(sorted_values: list[int])that constructs a height-balanced BST inO(n)time — without inserting one element at a time. Hint: recursively pick the middle element of each slice as the subtree root. For the input[1, 2, 3, 4, 5, 6, 7], a correct implementation should produce a tree with4at the root, matching the shape from Example 3.
Summary
- A plain BST’s height depends on insertion order and can degrade to
O(n)in the worst case (e.g., inserting already-sorted data); a balanced tree prevents this. - An AVL tree enforces that every node’s balance factor (left subtree height minus right subtree height) stays in
{-1, 0, 1}, guaranteeing heightO(log n)at all times. - Rebalancing uses four rotation cases — LL, RR (single rotation) and LR, RL (double rotation) — chosen by comparing the inserted key against the unbalanced node’s child’s key.
- Complexity: search, insert, and delete are all
O(log n)in the best, average, and worst case; space isO(n)for the nodes plusO(log n)for the recursion stack. - Each rotation itself is
O(1), and a single insertion never needs more than one (single or double) rotation, which is why insertion staysO(log n)overall. - Common bugs: forgetting to recompute heights after a rotation, and collapsing the four rotation cases down to two and silently mishandling the LR/RL zigzag cases.
- AVL trees trade faster lookups for costlier writes compared to Red-Black trees; choose based on whether your workload is read-heavy or write-heavy.
