The BST from the last lesson promised $O(\log n)$ search and insert — but that promise has fine print: only if the tree is balanced. Insert already sorted data and a BST silently turns into a linked list.

What you’ll learn

• Why a skewed BST loses its $O(\log n)$ guarantee entirely.
• AVL trees: the height-balance rule and how rotations restore it.
• Red-Black trees: coloring rules that give a looser, cheaper-to-maintain balance guarantee.
• The practical reality: Python has no built-in balanced BST — what to reach for instead (bisectbisect, sortedcontainers.SortedListsortedcontainers.SortedList).

Why balance matters

A BST’s height determines its speed. Insert values in sorted order and every new node becomes the rightmost node’s only child — you get a chain, not a tree:

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def bst_insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = bst_insert(root.left, val)
    else:
        root.right = bst_insert(root.right, val)
    return root
 
 
def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))
 
 
# Insert already-sorted data: worst case for a plain BST
root = None
for v in [1, 2, 3, 4, 5, 6, 7]:
    root = bst_insert(root, v)
 
print("nodes: 7, height:", height(root))   # height 6 -- a straight line, not a tree!

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def bst_insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = bst_insert(root.left, val)
    else:
        root.right = bst_insert(root.right, val)
    return root
 
 
def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))
 
 
# Insert already-sorted data: worst case for a plain BST
root = None
for v in [1, 2, 3, 4, 5, 6, 7]:
    root = bst_insert(root, v)
 
print("nodes: 7, height:", height(root))   # height 6 -- a straight line, not a tree!

  graph TD
    subgraph BAL["Balanced, height=2"]
        A((4)) --> B((2))
        A --> C((6))
        B --> D((1))
        B --> E((3))
        C --> F((5))
        C --> G((7))
    end
    subgraph SKEW["Skewed, height=6"]
        H((1)) --> I((2))
        I --> J((3))
        J --> K((4))
        K --> L((5))
        L --> M((6))
        M --> N((7))
    end

Both trees hold the same 7 values. The balanced one answers “is 7 present?” in 3 comparisons; the skewed one needs 7 — it’s just a linked list wearing a tree costume. Self-balancing trees exist to prevent exactly this.

AVL trees: strict height balance

An AVL tree enforces a simple invariant at every node: the heights of its left and right subtrees can differ by at most 11.

Whenever an insert or delete breaks that invariant, the tree fixes itself with a rotation — a local restructuring that restores balance in $O(1)$ without changing the sorted (inorder) order of the values.

  graph LR
    subgraph BEFORE["Before: imbalanced"]
        A2((10)) --> B2((5))
        A2 --> C2((20))
        C2 --> D2((15))
        C2 --> E2((30))
        E2 --> F2((40))
    end
    subgraph AFTER["After: left rotation at 20"]
        A3((20)) --> B3((10))
        A3 --> C3((30))
        B3 --> D3((5))
        B3 --> E3((15))
        C3 --> F3((40))
    end

Before: node 2020’s right subtree (rooted at 3030) is taller than its left (1515), so 2020 becomes right-heavy. A left rotation promotes 2020’s right child (3030)… conceptually — in this small example the rotation re-centers the tree around 2020 so both subtrees end up height-balanced again, without breaking the BST ordering. There are four rotation cases in total (left-left, right-right, left-right, right-left), but they all boil down to the same idea: re-parent a few pointers, keep the sort order, restore the height rule.

Because AVL rebalances aggressively, it guarantees $O(\log n)$ height at all times — the tightest balance guarantee of the common self-balancing trees, at the cost of more rotations on insert/delete-heavy workloads.

Red-Black trees: looser balance, cheaper to maintain

A Red-Black tree relaxes AVL’s strict rule and instead colors every node red or black, enforcing:

1. The root is always black.
2. A red node never has a red child (no two reds in a row on any path).
3. Every path from a node to its descendant NoneNone leaves passes through the same number of black nodes.

These rules don’t force perfect height-balance like AVL does, but they guarantee the longest root-to-leaf path is never more than 2x the shortest one — still $O(\log n)$ height, just with fewer rotations needed on average. That trade-off (looser balance, cheaper maintenance) is why Red-Black trees back most language standard libraries: C++‘s std::mapstd::map / std::setstd::set, Java’s TreeMapTreeMap, and the Linux kernel’s scheduler.

The Python reality: no built-in balanced BST

Unlike C++ or Java, Python’s standard library ships no self-balancing tree. dictdict and setset are hash tables ($O(1)$ average, but no ordering). For competitive programming and interviews, you have two practical substitutes:

1. bisectbisect on a plain sorted list — no extra dependency, $O(\log n)$ search, $O(n)$ insert (due to shifting), fine for small/medium nn.
2. sortedcontainers.SortedListsortedcontainers.SortedList — a third-party package (allowed on most judges and installable via pippip) implemented as a list of small sorted blocks, giving $O(\log n)$ search and $O(\sqrt{n})$-ish amortized insert/delete in practice — close to a real balanced tree’s behavior, usable from pure Python.

import bisect
 
# Maintain an always-sorted list using bisect -- Python's go-to
# "ordered set" substitute when a full balanced tree is overkill.
ordered = []
for value in [50, 20, 70, 10, 60, 30]:
    bisect.insort(ordered, value)
    print(f"after inserting {value}:", ordered)
 
target = 30
idx = bisect.bisect_left(ordered, target)
found = idx < len(ordered) and ordered[idx] == target
print("30 present?", found, "at sorted index", idx)
 
# rank of a value == how many elements are strictly smaller -- O(log n) to find
rank = bisect.bisect_left(ordered, 60)
print("elements smaller than 60:", rank)

import bisect
 
# Maintain an always-sorted list using bisect -- Python's go-to
# "ordered set" substitute when a full balanced tree is overkill.
ordered = []
for value in [50, 20, 70, 10, 60, 30]:
    bisect.insort(ordered, value)
    print(f"after inserting {value}:", ordered)
 
target = 30
idx = bisect.bisect_left(ordered, target)
found = idx < len(ordered) and ordered[idx] == target
print("30 present?", found, "at sorted index", idx)
 
# rank of a value == how many elements are strictly smaller -- O(log n) to find
rank = bisect.bisect_left(ordered, 60)
print("elements smaller than 60:", rank)

Complexity at a glance

Where this shows up in contests

You rarely implement AVL/Red-Black rotations yourself in a contest — instead you recognize the need for an ordered, dynamically-updated set and reach for SortedListSortedList (or bisectbisect, or a Fenwick tree / segment tree, covered later). Watch for phrasing like “maintain the k smallest values seen so far,” “process queries online,” or “find the number of elements less than x after each update” — all signals that a balanced-tree-like structure is the intended tool.

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 110 — Balanced Binary Tree · Easy

Problem. Return TrueTrue if the tree is height-balanced — every node’s two subtrees differ in height by at most one.

Constraints. 0 <= number of nodes <= 50000 <= number of nodes <= 5000.

Examples. [3,9,20,null,null,15,7][3,9,20,null,null,15,7] gives TrueTrue · [1,2,2,3,3,null,null,4,4][1,2,2,3,3,null,null,4,4] gives FalseFalse · [][] gives TrueTrue

LC 108 — Convert Sorted Array to Binary Search Tree · Easy

Problem. Given a sorted array of unique integers, build a height-balanced BST.

Constraints. 1 <= len(nums) <= 10^41 <= len(nums) <= 10^4, strictly increasing.

Examples. [-10,-3,0,5,9][-10,-3,0,5,9] gives a balanced BST of height 3 · [1,3][1,3] gives height 2

LC 1382 — Balance a Binary Search Tree · Medium

Problem. Given a BST, return a balanced BST containing the same values.

Constraints. 1 <= number of nodes <= 10^41 <= number of nodes <= 10^4, 1 <= Node.val <= 10^51 <= Node.val <= 10^5, values unique.

Examples. A right-leaning chain [1,null,2,null,3,null,4][1,null,2,null,3,null,4] becomes a balanced tree of height 3

Recap

• An unbalanced BST degrades to $O(n)$ on adversarial (e.g. sorted) input — height is the whole game.
• AVL trees enforce strict height balance via rotations after every insert/delete: fastest lookups, more rebalancing work.
• Red-Black trees use coloring rules for a looser but still $O(\log n)$-height guarantee: cheaper writes, standard in most language libraries.
• Python has no built-in balanced BST — use bisectbisect on a list for light use, or sortedcontainers.SortedListsortedcontainers.SortedList when you need real $O(\log n)$ ordered inserts/deletes.

Next: Tries — a tree specialized for strings, giving $O(L)$ prefix operations regardless of how many words you’ve stored.