Balanced Trees
Why shape matters.
A binary search tree is only fast if it's bushy, with roughly the same number of nodes on each side. If values arrive already sorted, every new value goes to the right, and the tree becomes one long chain. Then it's no better than a linked list.

- Fast only when bushy
- Sorted input makes a chain
- A chain is a linked list
Same values, different shapes
We insert the numbers one to a hundred and twenty seven twice. Once in sorted order, and once in a shuffled order. Then we measure the height of each tree. Run it. The sorted tree is a chain, a hundred and twenty seven levels tall. The shuffled tree is only sixteen levels. Searching is O of height, so shape is everything.
import random
from bst import insert, height
values = list(range(1, 128))
chain = None
for v in values:
chain = insert(chain, v)
random.seed(1)
random.shuffle(values)
bushy = None
for v in values:
bushy = insert(bushy, v)
print("sorted order height: ", height(chain))
print("shuffled order height:", height(bushy))sorted order height: 127 shuffled order height: 16
Also uses bst.py
class Node:
def __init__(self, value):
self.value, self.left, self.right = value, None, None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def height(n):
return 1 + max(height(n.left), height(n.right)) if n else 0Self balancing trees
Real systems use self balancing trees, like AVL trees, and red black trees. After each insert, they rotate nodes to keep the tree bushy, so the height stays O of log N, whatever order the values arrive in. You rarely write one yourself, but you should know they exist, and why.
| key | value |
|---|---|
| Unbalanced | O(n) worst case |
| Balanced | O(log n) height |
| AVL, red-black | rebalance on insert |
| Rotations | keep it bushy |
Summary
A tree's height decides its speed. Sorted input makes a chain, and self balancing trees prevent that. Next, practice. Is this tree a valid binary search tree?
Key takeaways- Height = speed
- Sorted input → chain
- Balanced → O(log n)