Introduction

A balanced binary search tree keeps lookup, insertion, and deletion close to O(log n) by preventing the tree from degenerating into a linked list. In practice, the easiest way to understand implementation is to pick one concrete strategy, and AVL trees are a good starting point because their balancing rules are explicit.

Start With the Node Structure

An AVL tree stores the normal BST fields plus enough metadata to decide when rebalancing is needed. The usual metadata is node height.

1class Node:
2    def __init__(self, key):
3        self.key = key
4        self.left = None
5        self.right = None
6        self.height = 1

The height field lets the tree compute balance factors after insertions or deletions.

The Balance Rule

In an AVL tree, each node must keep the height difference between its left and right subtrees within one. That difference is the balance factor:

• positive means left-heavy
• negative means right-heavy
• zero means evenly balanced

1def height(node):
2    return node.height if node else 0
3
4
5def balance_factor(node):
6    return height(node.left) - height(node.right) if node else 0

When the balance factor moves outside the allowed range, rotations restore balance.

Implement Rotations

Rotations are the core balancing operation. A left rotation fixes a right-heavy subtree, and a right rotation fixes a left-heavy subtree.

1def update_height(node):
2    node.height = 1 + max(height(node.left), height(node.right))
3
4
5def rotate_right(y):
6    x = y.left
7    t2 = x.right
8
9    x.right = y
10    y.left = t2
11
12    update_height(y)
13    update_height(x)
14    return x
15
16
17def rotate_left(x):
18    y = x.right
19    t2 = y.left
20
21    y.left = x
22    x.right = t2
23
24    update_height(x)
25    update_height(y)
26    return y

These are local structural changes that preserve the binary-search-tree ordering while reducing imbalance.

Insert and Rebalance

Insertion starts like a normal BST insert. The difference is what happens on the way back up the recursion: update heights, compute balance, and rotate if needed.

1def insert(node, key):
2    if node is None:
3        return Node(key)
4
5    if key < node.key:
6        node.left = insert(node.left, key)
7    elif key > node.key:
8        node.right = insert(node.right, key)
9    else:
10        return node
11
12    update_height(node)
13    balance = balance_factor(node)
14
15    if balance > 1 and key < node.left.key:
16        return rotate_right(node)
17
18    if balance < -1 and key > node.right.key:
19        return rotate_left(node)
20
21    if balance > 1 and key > node.left.key:
22        node.left = rotate_left(node.left)
23        return rotate_right(node)
24
25    if balance < -1 and key < node.right.key:
26        node.right = rotate_right(node.right)
27        return rotate_left(node)
28
29    return node

Those four cases correspond to the classic AVL imbalance patterns:

• left-left
• right-right
• left-right
• right-left

Traversal Still Looks Familiar

Balancing changes tree shape, but traversal code still looks like ordinary BST code.

1def inorder(node):
2    if not node:
3        return []
4    return inorder(node.left) + [node.key] + inorder(node.right)
5
6
7root = None
8for value in [10, 20, 30, 40, 50, 25]:
9    root = insert(root, value)
10
11print(inorder(root))

An inorder traversal should still return the keys in sorted order. That is a good basic correctness check.

Why You Might Not Write One in Production

Balanced BSTs are a great data-structure exercise, but production code often uses a library implementation unless you truly need a custom tree. The algorithm is not just about insertion. Deletion, iteration, testing, edge cases, and performance tuning all add complexity quickly.

That is why interview or educational implementations often stop at insertion plus rotations: the balancing idea is the real lesson.

Common Pitfalls

The biggest mistake is updating the tree shape without updating node heights afterward. Once height metadata is wrong, later balance decisions become wrong too.

Another common issue is forgetting the double-rotation cases. Single rotations only fix the simple left-left and right-right cases.

People also sometimes try to rebalance before finishing the recursive insertion path. The usual pattern is insert first, then update metadata and rotate on the way back out.

Finally, do not confuse "balanced BST" with "perfectly balanced tree." A self-balancing tree only guarantees a logarithmic-height bound, not a perfectly symmetrical shape.

Summary

• A balanced BST keeps operations near O(log n) by preventing pathological height growth.
• AVL trees track node height and rebalance when the balance factor leaves the allowed range.
• Rotations preserve BST ordering while fixing local imbalance.
• Insert first, then update heights and rebalance on the way back up.
• Production use often favors library implementations, but AVL insertion is a strong way to learn the mechanics.