AmouAI Hub/Courses/Data Structures & Algorithms/Chapter 15

Part 4 · Trees · Chapter 15

Binary Search Trees

A binary search that lives in the structure itself. Beautiful when balanced, and quietly catastrophic when you insert sorted data — which happens more often than you would think.

Reading

CLRS Ch. 12

Focus

Order in the shape

Cost

O(h) — log n or n

Balancing, Ch. 16

By the end of this chapter you can

State the BST property precisely, including the trap in the naive version
Implement search, insert and the three deletion cases
Explain why deleting a node with two children needs the in-order successor specifically
Demonstrate degeneration and say which real-world inputs cause it
Choose between a BST and a hash table for a stated access pattern

1The property

One rule, applied at every node. It turns a tree into a search structure and makes in-order traversal produce sorted output.

The guessing game, made physical

Chapter 13's binary search halved a sorted array by computing a midpoint. A BST does the same thing, but the halving is built into the shape: at every node you are told which way to go, and the other subtree disappears.

The array had to be sorted, which made insertion O(n). The tree stays searchable while also allowing cheap insertion — that is the trade it buys.

The binary search tree property, stated carefully:

The BST property

For every node n:

every value in n's entire left subtree is less than n.value
every value in n's entire right subtree is greater than n.value

Note entire subtree, not just the immediate children. This is the distinction the naive validity check gets wrong, and section 5 shows exactly how.

bst.py

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

#           50
#          /  \
#        30    70
#       /  \   / \
#     20   40 60  80
#
# In-order traversal: 20 30 40 50 60 70 80 — sorted, necessarily.

Two consequences follow immediately, and both are worth stating out loud:

In-order traversal gives sorted output. Chapter 14 showed why: in-order visits everything smaller, then the node, then everything larger.
Search is a single root-to-leaf walk. Every comparison sends you one way and discards the entire other subtree.

2Search and insert

Both are the same walk. Search stops when it finds the value; insert stops when it runs off the end and puts the value there.

search_insert.py

def search(node, target):
    while node is not None:
        if target == node.value:
            return node
        node = node.left if target < node.value else node.right
    return None                       # ran off the bottom: not present


def insert(node, value):
    """Returns the (possibly new) subtree root."""
    if node is None:
        return Node(value)            # the empty slot we walked to
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    # equal: do nothing — this BST holds distinct values
    return node

Notice the structure of insert. It returns the subtree root and the caller reassigns it. That pattern — node.left = insert(node.left, value) — means the code never has to track a parent pointer, and it handles the empty-tree case with no special branch. It is worth internalising, because deletion and the rotations in Chapter 16 use exactly the same shape.

O(h)

Insert

O(h)

Delete

O(h)

Min / max

O(h)

In-order walk

O(n)

Space

O(n)

Everything is O(h), so everything depends on the height. Which is the next section's problem.

The easy extras

Because the property is directional, minimum and maximum are trivial:

extras.py

def minimum(node):
    while node.left is not None:      # smallest = leftmost, always
        node = node.left
    return node

def maximum(node):
    while node.right is not None:     # largest = rightmost, always
        node = node.right
    return node

# And range queries, which a hash table cannot do at all:
def values_between(node, lo, hi, out):
    if node is None:
        return
    if node.value > lo:                    # prune: nothing smaller is left of here
        values_between(node.left, lo, hi, out)
    if lo <= node.value <= hi:
        out.append(node.value)
    if node.value < hi:                    # prune the other way
        values_between(node.right, lo, hi, out)

The pruning is the point

Those two if guards in values_between are what make a range query O(h + k) for k results rather than O(n). Without them you would walk the whole tree.

This is the operation a hash table cannot do at all. It is the main reason BSTs still exist in a world with dictionaries.

3Deletion, and its three cases

The one genuinely fiddly BST operation, because the tree must still be a valid BST afterwards.

Removing a node leaves a hole, and what fills it depends on how many children the node had. There are exactly three cases.

Case 1 — a leaf

Nothing depends on it. Cut it off.

Case 2 — one child

The child's whole subtree moves up into the deleted node's place. This is safe because every value in that subtree was already on the correct side of the grandparent.

Case 3 — two children

Here you cannot simply promote a child, because the other one would have nowhere to go. Instead find the in-order successor: the smallest value in the right subtree.

Why the successor specifically

The replacement value must be larger than everything in the left subtree and smaller than everything in the right subtree. There are exactly two values with that property: the largest in the left subtree (the predecessor) and the smallest in the right subtree (the successor). Either works; convention picks the successor.

And the recursion terminates, because the successor is the leftmost node of the right subtree — so it has no left child, and deleting it is guaranteed to be Case 1 or Case 2.

delete.py

def delete(node, value):
    if node is None:
        return None

    if value < node.value:
        node.left = delete(node.left, value)
    elif value > node.value:
        node.right = delete(node.right, value)
    else:
        # found it — three cases
        if node.left is None:
            return node.right          # covers leaf (returns None) AND one right child
        if node.right is None:
            return node.left           # one left child

        # two children: copy the successor's value up, then delete it below
        succ = node.right
        while succ.left is not None:
            succ = succ.left
        node.value = succ.value
        node.right = delete(node.right, succ.value)

    return node

Cases 1 and 2 collapse into two lines

if node.left is None: return node.right handles the leaf case too — because a leaf's right is also None, so it returns None, which is exactly “cut it off.”

Three cases in the explanation, two lines in the code. Worth noticing when a case analysis collapses like this.

4Degeneration

Everything above is O(h). Here is what makes h go wrong, and why the input that causes it is so common.

The BST's costs are all O(h), and h depends entirely on the order values were inserted. The same set of values can produce a beautifully balanced tree or a straight line.

Every value is larger than the last, so every insert goes right, and the tree is a linked list with extra pointers. Search is now O(n) — and it is slower than a plain array, because it has none of the cache locality.

Insertion order	Resulting height (n = 7)	Search cost
Balanced: 50, 30, 70, 20, 40, 60, 80	2	O(log n) — 3 comparisons
Random	about 2 log₂ n on average	O(log n)
Sorted: 10, 20, 30, 40, 50, 60, 70	6	O(n) — 7 comparisons
Reverse sorted	6	O(n)

Sorted input is not a rare edge case

It is the normal case. Consider:

Rows read from a database with an ORDER BY.
Timestamps from a log file.
Auto-incrementing IDs.
The output of any previous sort in your pipeline.

A plain BST fed real-world data very often degenerates. That is not a theoretical concern; it is why nobody ships a plain BST.

The good news is that random insertion order gives an expected height of about 2 log₂ n — so a BST is fine on average. The bad news is that you rarely control the insertion order, and the bad cases are the likely ones.

Three ways out, in increasing order of seriousness:

Shuffle before inserting. Works if you have all the data up front, which you usually do not.
Randomise the structure. A treap or skip list uses randomness internally to get O(log n) with high probability.
Rebalance on every insert. AVL and red-black trees. This is what real libraries do, and it is Chapter 16.

5Validating a BST, and BST vs hash table

A famous interview question with a famous wrong answer, and then the practical decision this chapter exists to inform.

The wrong validity check

wrong_validity.py

def is_bst_WRONG(node):
    if node is None:
        return True
    if node.left and node.left.value >= node.value:
        return False
    if node.right and node.right.value <= node.value:
        return False
    return is_bst_WRONG(node.left) and is_bst_WRONG(node.right)

#        10
#       /  \
#      5    15
#          /  \
#         6    20      ← 6 < 10, but it is in the RIGHT subtree of 10
#
# Every parent-child pair is fine: 6 < 15 ✓, and 15 > 10 ✓.
# The tree is still not a BST — searching for 6 would go RIGHT at 10
# and never find it.

The property is about entire subtrees, so the check must carry a range down the tree:

correct_validity.py

def is_bst(node, lo=float("-inf"), hi=float("inf")):
    if node is None:
        return True
    if not (lo < node.value < hi):
        return False
    return (is_bst(node.left,  lo, node.value) and    # tighten the upper bound
            is_bst(node.right, node.value, hi))       # tighten the lower bound

# Going left, everything must now be below this node's value.
# Going right, everything must be above it. The bounds narrow as you
# descend, and that is exactly the property stated recursively.


# The other correct check: in-order must be strictly increasing.
def is_bst_inorder(root):
    prev = None
    for value in inorder(root):
        if prev is not None and value <= prev:
            return False
        prev = value
    return True

BST or hash table?

Both give you “look up a key.” The choice is decided entirely by whether you need order.

Operation	Hash table	Balanced BST
Lookup by key	O(1) average	O(log n)
Insert / delete	O(1) average	O(log n)
Worst case	O(n)	O(log n) guaranteed
Iterate in sorted order	O(n log n) — must sort	O(n) — in-order walk
Minimum / maximum	O(n)	O(log n)
Range query (10 ≤ k ≤ 20)	O(n) — scan everything	O(log n + k)
Successor / predecessor of k	O(n)	O(log n)
Memory per entry	Higher (empty slots)	Lower
Keys must be	Hashable	Comparable

The one-line decision

Do you ever need the keys in order?

No — use a hash table. It is faster and simpler, and that is why dict is the Python default.

Yes — use a balanced tree. Sorted iteration, range queries, “the next key after x”, and “the smallest key” are all things a hash table simply cannot do without a full scan.

This is why C++ has both unordered_map (hash) and map (red-black tree), and why Java has both HashMap and TreeMap. Python ships only the hash version in the standard library — for the tree behaviour you reach for sortedcontainers or keep a sorted list with bisect.

What to carry forward

The BST property is about entire subtrees, not parent-child pairs. That distinction is what makes the naive validity check wrong.
Search, insert and delete are all O(h), one root-to-leaf walk. Everything depends on the height.
node.left = insert(node.left, v) — return the subtree root and let the caller reassign. No parent pointers, no special cases.
Deletion has three cases; the two-children case needs the in-order successor, and that deletion is guaranteed to be an easy case.
Sorted input degenerates a BST into a linked list. And sorted input is the normal case — database rows, timestamps, auto-increment IDs.
Hash table unless you need order. Sorted iteration, ranges, min/max and successor are what a BST buys, and a hash table cannot do any of them.

>_Playground

A complete BST. Insert in different orders and watch the height change — that is the whole story of this chapter.

scratch.pypython not loaded

class Node:
    def __init__(self, value):
        self.value, self.left, self.right = value, None, None

def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node

def search(node, target):
    steps = 0
    while node is not None:
        steps += 1
        if target == node.value:
            return True, steps
        node = node.left if target < node.value else node.right
    return False, steps

def height(node):
    return -1 if node is None else 1 + max(height(node.left), height(node.right))

def inorder(node, out=None):
    out = [] if out is None else out
    if node:
        inorder(node.left, out); out.append(node.value); inorder(node.right, out)
    return out

def show(node, depth=0):
    if node is None: return
    show(node.right, depth + 1)
    print("      " * depth + str(node.value))
    show(node.left, depth + 1)

def build(values):
    root = None
    for v in values:
        root = insert(root, v)
    return root

values = [50, 30, 70, 20, 40, 60, 80]

balanced = build(values)
print("--- inserted in balanced order ---")
show(balanced)
print("height:", height(balanced), "  in-order:", inorder(balanced))
print("search 80 ->", search(balanced, 80))
print()

degenerate = build(sorted(values))
print("--- inserted in SORTED order (same seven values) ---")
show(degenerate)
print("height:", height(degenerate), "  in-order:", inorder(degenerate))
print("search 80 ->", search(degenerate, 80))
print()

# --- how bad does it get at scale? ---
import random
random.seed(0)
n = 2000

shuffled = list(range(n)); random.shuffle(shuffled)
import sys; sys.setrecursionlimit(10000)
h_random = height(build(shuffled))

# building the sorted one recursively would blow the stack, so do it iteratively
root = Node(0); cur = root
for i in range(1, n):
    cur.right = Node(i); cur = cur.right
h_sorted = n - 1

print(f"n = {n}")
print(f"  random insertion order : height {h_random:5}   (~2*log2(n) = {2*11})")
print(f"  sorted insertion order : height {h_sorted:5}   <- a linked list")
print()
print("Same values. Same code. 200x difference in search cost.")

Real Python, running in your browser. Nothing is installed or uploaded.

Output appears here. The first run takes a few seconds while Python loads.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.

All Warm-up Core Challenge Reset chapter

Chapter 16 — Self-Balancing Trees: AVL and Red-Black

If a BST can degenerate, make it repair itself. Rotations look like sleight of hand until you see one animated.

Continue →