AI Hints
Home›DSA in Python Tutorial›Tree Practice
DSA in Python · Lesson 67 of 132

Balanced Trees

Why shape matters.

⏱ 2 min read▶ Video at 1:18:54🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Balanced Trees
From the video: Balanced Trees
  • 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.

shapes.pypython
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))
Output
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 0

Self 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.

keyvalue
UnbalancedO(n) worst case
BalancedO(log n) height
AVL, red-blackrebalance on insert
Rotationskeep 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)
Next up: Practice: Validate a BST — checking the rule everywhere