The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Binary Search Trees

Next ►
►

This is the lesson where the module pays its debts. Module 5's hash table fell silent at "give me the tasks ordered by id" and "the ones with priority between 1 and 3"; the inorder traversal of 06-03 came out mysteriously sorted. Both have the same explanation: the binary search tree (BST), a binary tree with a placement rule — smaller to the left, larger to the right — that turns every comparison into discarding half a tree. Here you'll implement the complete SearchTree class (insert, find, minimum/maximum, delete with its three cases, sorted traversal, and range search), use it as TaskFlow's task index, and also discover its Achilles' heel: with data that arrives already sorted, the BST degenerates into a list and everything becomes O(n) — the problem that will motivate the next lesson.

Contents

  1. The BST property: one rule, all the consequences
  2. Finding and inserting: descend by comparing
  3. Minimum, maximum, and the inorder that comes out sorted
  4. Deleting: the three cases
  5. Range search: module 5's debt, settled
  6. The cost is O(height): the degenerate tree demo
  7. dict vs BST: each to its own

The BST property: one rule, all the consequences

A binary search tree is a binary tree where, for every node with key k:

  • All the keys in its left subtree are smaller than k.
  • All the keys in its right subtree are larger than k.
graph TD
    A((10)) --> B((6))
    A --> C((15))
    B --> D((3))
    B --> E((8))
    C --> F((12))
    C --> G((20))

The tree from 06-03 was exactly this. Check the property at the root: to the left of 10 are {6, 3, 8}, all smaller; to the right, {15, 12, 20}, all larger. And mind the word all: it's not enough for each child to respect its parent — 8 is the right child of 6 (correct: 8 > 6), but it must also be smaller than 10, because it lives in the root's left subtree. This distinction between "local rule" and "rule over the whole subtree" is the classic mistake when validating a BST, and we'll hunt it down in 06-08.

The operational consequence: standing at any node, a single comparison tells you which half to continue into — just like the binary search of module 1, but on a linked structure that also allows cheap insertions and deletions (the sorted array searched in O(log n) but inserted in O(n) by shifting elements). The BST is, conceptually, binary search turned into a data structure.

Finding and inserting: descend by comparing

Let's build the full class. Each node will store a key (what it's ordered by) and a value (the TaskFlow task), as in the HashTable:

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

class SearchTree:
    """Ordered index: key -> value, with traversals and ranges."""

    def __init__(self):
        self.root = None

    def find(self, key):
        """Returns the value associated with the key, or None if absent. O(height)."""
        node = self.root
        while node is not None:
            if key == node.key:
                return node.value
            elif key < node.key:
                node = node.left       # smaller can only be on the left
            else:
                node = node.right      # larger, on the right
        return None

find is the decision-tree descent from 06-02, with the question "is the key I'm looking for smaller than mine?". Each comparison goes down one level and discards the entire other subtree: that's why the cost is O(height), not O(n). Inserting follows the same path — a new key's position is exactly where the search would have fallen off the tree:

    def insert(self, key, value):
        """Inserts the pair (or updates the value if the key exists). O(height)."""
        if self.root is None:
            self.root = BSTNode(key, value)
            return
        node = self.root
        while True:
            if key == node.key:
                node.value = value                     # repeated key: update
                return
            elif key < node.key:
                if node.left is None:
                    node.left = BSTNode(key, value)
                    return
                node = node.left
            else:
                if node.right is None:
                    node.right = BSTNode(key, value)
                    return
                node = node.right

Let's build the task index by id (we use integer ids for easy comparison):

index = SearchTree()
tasks = [
    (10, {"id": 10, "title": "Deploy API", "priority": 2, "status": "pending"}),
    (6,  {"id": 6,  "title": "Review login", "priority": 1, "status": "in_progress"}),
    (15, {"id": 15, "title": "Back up data", "priority": 3, "status": "pending"}),
    (3,  {"id": 3,  "title": "Fix CSS", "priority": 2, "status": "pending"}),
    (8,  {"id": 8,  "title": "Migrate data", "priority": 1, "status": "blocked"}),
    (12, {"id": 12, "title": "Optimize queries", "priority": 2, "status": "pending"}),
    (20, {"id": 20, "title": "Document API", "priority": 3, "status": "pending"}),
]
for task_id, task in tasks:
    index.insert(task_id, task)

print(index.find(8)["title"])    # Migrate data
print(index.find(99))            # None

The insertion order (10 first, then 6, 15...) has built exactly the tree in the diagram. Hold on to this fact: the shape of a BST depends on the arrival order of the keys. It will come back to bite us in section 6.

Minimum, maximum, and the inorder that comes out sorted

The BST property gives us three operations the hash table can't even dream of:

    def minimum(self):
        """The smallest key: all the way left. O(height)."""
        if self.root is None:
            return None
        node = self.root
        while node.left is not None:
            node = node.left
        return node.key

    def maximum(self):
        """The largest key: all the way right. O(height)."""
        if self.root is None:
            return None
        node = self.root
        while node.right is not None:
            node = node.right
        return node.key

    def inorder(self):
        """All (key, value) pairs in ascending key order. O(n)."""
        result = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node, result):
        if node is None:
            return
        self._inorder(node.left, result)
        result.append((node.key, node.value))
        self._inorder(node.right, result)
print(index.minimum(), index.maximum())        # 3 20
print([key for key, _ in index.inorder()])     # [3, 6, 8, 10, 12, 15, 20]

And here 06-03's announcement comes true: the inorder of a BST returns the keys sorted, always. The proof fits in two lines: inorder visits left → node → right; by the BST property, everything on the left is smaller than the node and everything on the right larger; applying the same argument recursively to each subtree, the whole output ends up ascending. "Give me the tasks ordered by id" — the first question that left the HashTable speechless — is now a call to inorder(), in O(n) and without sorting anything: the tree maintains order as a permanent invariant, instead of computing it on demand as sorted() would (O(n log n) every time).

Deleting: the three cases

Deleting is the delicate operation: you have to remove the node without breaking the property for everyone else. Three cases, from easy to hard:

Case Situation Solution
1 The node is a leaf Unhook it from the parent, that's all
2 It has a single child The child takes its place (like skipping a node in the linked list)
3 It has two children Replace it with its successor and delete the successor

Case 3 deserves an explanation. We can't leave a hole with two subtrees dangling; we need a replacement that preserves "left smaller, right larger". The perfect candidate is the inorder successor: the smallest key in the right subtree (the node that would come out right after it in inorder). It's larger than the whole left subtree (it's on the right) and smaller than the rest of the right subtree (it's its minimum) — it fits exactly. And removing it from its original position is easy: being the minimum of a subtree, it has no left child (case 1 or 2 guaranteed). The symmetric choice (maximum of the left subtree, the predecessor) works just as well.

graph TD
    subgraph "Delete 10 (two children)"
        A((10)) --> B((6))
        A --> C((15))
        C --> F((12))
        C --> G((20))
    end
    subgraph "The successor 12 replaces it"
        A2((12)) --> B2((6))
        A2 --> C2((15))
        C2 -.deleted.-> F2((12))
        C2 --> G2((20))
    end

The recursive implementation is the cleanest — each call returns the (possibly new) root of its subtree, and the parent re-hooks it; the same "rebuild on the way back" pattern we'll use in the AVL tree:

    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, node, key):
        if node is None:
            return None                              # key not found: nothing to do
        if key < node.key:
            node.left = self._delete(node.left, key)
        elif key > node.key:
            node.right = self._delete(node.right, key)
        else:
            # Found. Cases 1 and 2: zero or one child
            if node.left is None:
                return node.right                    # may be None (leaf case)
            if node.right is None:
                return node.left
            # Case 3: two children -> successor = minimum of the right subtree
            successor = node.right
            while successor.left is not None:
                successor = successor.left
            node.key, node.value = successor.key, successor.value   # copy the successor here
            node.right = self._delete(node.right, successor.key)    # and delete it from there
        return node
index.delete(10)      # the root, with two children: the hard case
print([k for k, _ in index.inorder()])     # [3, 6, 8, 12, 15, 20] — still sorted
print(index.root.key)                      # 12: the successor took the root

Read it twice — it deserves it: cases 1 and 2 are solved by returning the child (or None) for the parent to adopt; case 3 doesn't remove the physical node but copies the successor's data into it and delegates the actual removal to an easy case. Total cost: O(height) — one descent to find, another partial one for the successor.

Range search: module 5's debt, settled

The question the hash table couldn't even formulate: "all tasks with key between a and b". In the BST, the property enables pruning: if a node's key is already smaller than a, its entire left subtree is out of range — we don't even visit it.

    def range_query(self, low, high):
        """(key, value) pairs with low <= key <= high, in order. O(height + k)."""
        result = []
        self._range_query(self.root, low, high, result)
        return result

    def _range_query(self, node, low, high, result):
        if node is None:
            return
        if node.key > low:                   # there may be candidates on the left
            self._range_query(node.left, low, high, result)
        if low <= node.key <= high:          # does this node qualify?
            result.append((node.key, node.value))
        if node.key < high:                  # there may be candidates on the right
            self._range_query(node.right, low, high, result)

It's an inorder with two brakes: it only enters a subtree if the range can reach it. The cost is O(height + k), with k results: getting down to the range costs the height, and from there on you only step on what you return (plus a boundary strip). Compared with the hash: there, the only option was to scan EVERYTHING and filter, O(n) always.

What about "priority between 1 and 3"? Priority isn't unique (many tasks share a priority) and our BST wants distinct keys. The professional trick, the same as the (priority, counter, task) of module 4's UrgentInbox: a composite key (priority, id) — tuples compare lexicographically, so it orders by priority and breaks ties by id, and each pair is unique:

by_priority = SearchTree()
for task_id, task in tasks:
    by_priority.insert((task["priority"], task_id), task)

# Module 5's debt: tasks with priority between 1 and 3
urgent = by_priority.range_query((1, 0), (3, float("inf")))
for (prio, task_id), task in urgent:
    print(prio, task_id, task["title"])
# 1 6  Review login
# 1 8  Migrate data
# 2 3  Fix CSS
# ...ordered by (priority, id), from 1 through 3

The bounds (1, 0) and (3, float("inf")) bracket "any id with priority 1" from below and "any id with priority 3" from above. Query answered, sorted as a bonus, pruning everything irrelevant. This is the row of 06-01's table that was left blank.

The cost is O(height): the degenerate tree demo

Everything above costs O(height), and we've been hinting that height can betray us. Time to cause the disaster. What happens if the keys arrive already sorted — the most natural case in the world: auto-incrementing ids, tasks created in order?

sequential = SearchTree()
for i in range(1, 8):
    sequential.insert(i, f"task {i}")

Each new key is larger than all the previous ones, so it always goes down the right side:

graph TD
    A((1)) --> B((2))
    B --> C((3))
    C --> D((4))
    D --> E((5))
    E --> F((6))
    F --> G((7))

The degenerate tree from 06-02: a linked list with a tree's name. Height n−1, and the whole cost table collapses:

Operation Balanced BST Degenerate BST
find O(log n) O(n)
insert O(log n) O(n)
delete O(log n) O(n)
minimum / maximum O(log n) O(n)

Let's measure it with timeit, as in module 1 — building the index with 2,000 sorted ids versus the same ids shuffled:

import timeit, random, sys
sys.setrecursionlimit(10000)     # recursive inorder on a degenerate tree needs it

ids = list(range(2000))
shuffled = ids[:]
random.shuffle(shuffled)

def build(keys):
    t = SearchTree()
    for k in keys:
        t.insert(k, None)
    return t

print(timeit.timeit(lambda: build(ids), number=5))       # ~4 s   (O(n²) total!)
print(timeit.timeit(lambda: build(shuffled), number=5))  # ~0.03 s (O(n log n))

(The exact times depend on your machine; the ratio — two orders of magnitude — doesn't.) With random keys, the BST ends up reasonably balanced on average and the 2,000 insertions cost O(n log n) in total; with sorted keys, the i-th insertion walks i nodes and the total is O(n²). And the irony is cruel: the most common use case (auto-incrementing ids) is exactly the BST's worst case. An index that degrades precisely on the data it will receive most often is not a serious index. The fix — a tree that rebalances itself on every insertion — is the next lesson.

dict vs BST: each to its own

With both indexes built, the honest comparison (assuming a balanced BST; n elements, k results):

Operation dict / HashTable BST
Exact-key lookup O(1) O(log n)
Insert / delete O(1) O(log n)
Traverse in order O(n log n) (must sort) O(n) (inorder)
Minimum / maximum O(n) O(log n)
Range [a, b] O(n) (scan everything and filter) O(height + k)
Key requirement hashable mutually comparable

The right reading isn't "which one wins" but "for which question": exact key → hash; order, extremes, and ranges → tree. Real systems use both at once — TaskFlow too: the HashTable from 05-02 for get(id) in O(1), and this BST for listings and ranges. It's the same decision a database makes when choosing between a hash index and a tree index (we'll look at it up close in 06-06).

Common Mistakes and Tips

  • Validating the BST property by comparing only with the parent. A node must respect all its ancestors, not just the immediate one. The correct validator propagates bounds (minimum, maximum) as it descends — it's the star exercise of 06-08.
  • Deleting the two-children case "brute force". Replacing with just any child breaks the property. The replacement has to be the successor (minimum of the right subtree) or the predecessor (maximum of the left one) — only they fit between both subtrees.
  • Forgetting to reassign when calling _delete. The pattern node.left = self._delete(node.left, key) works because each call returns the new root of the subtree. Calling without assigning leaves the tree untouched, and the bug is silent.
  • Keys that aren't mutually comparable. Mixing int and str as keys blows up (TypeError on comparison). And with composite keys, mind the tuple order: (priority, id) orders by priority first; (id, priority) is a different index altogether.
  • Assuming "on average it balances itself". True with random keys, false with sorted or almost-sorted keys — which is what real systems produce (ids, timestamps). Don't count on luck: 06-05 exists because of this.

Exercises

Exercise 1: contains and the successor of a key

Add to SearchTree (a) contains(key) returning True/False, and (b) successor(key) returning the smallest key in the tree strictly greater than the given one (whether or not the given key exists in the tree), or None. With the lesson's index (after deleting 10): successor(8) → 12, successor(9) → 12, successor(20) → None.

Exercise 2: the pending tasks in the range

Using by_priority and range_query, write urgent_pending(tree, max_prio) that returns the titles of tasks with priority between 1 and max_prio whose status is "pending", ordered by (priority, id). The status filter is applied to the range result (the tree indexes by priority, not by status — one index per query).

Exercise 3: how tall is my tree?

Write bst_height(tree) (reuse 06-02's height on tree.root) and compare it on two indexes of 1,023 keys: one built with the sorted keys range(1023) and another with the same keys shuffled. What was the minimum possible height? Relate the three numbers.

Solutions

Solution 1

    def contains(self, key):
        # "find(key) is not None" isn't enough: a value could BE None.
        node = self.root
        while node is not None:
            if key == node.key:
                return True
            node = node.left if key < node.key else node.right
        return False

    def successor(self, key):
        candidate = None
        node = self.root
        while node is not None:
            if node.key > key:
                candidate = node.key       # it qualifies, but maybe there's a smaller one...
                node = node.left           # ...look for it on the left
            else:
                node = node.right          # too small: go right
        return candidate

print(index.successor(9))    # 12
print(index.successor(20))   # None

Comment: successor is the "best candidate so far" pattern: each node greater than the key is recorded as a candidate and we try to improve on it by going left; nodes less than or equal are discarded by going right. A single descent, O(height), and without requiring the key to exist. The subtle catch in contains is in the comment: in the demo we stored some tasks as None in the index, and find can't distinguish "not there" from "there, with value None" — the same nuance in versus get resolved in the dict.

Solution 2

def urgent_pending(tree, max_prio):
    result = []
    for (prio, task_id), task in tree.range_query((1, 0), (max_prio, float("inf"))):
        if task["status"] == "pending":
            result.append(task["title"])
    return result

print(urgent_pending(by_priority, 2))
# ['Fix CSS', 'Deploy API', 'Optimize queries']
# (the priority-1 ones were "in_progress" and "blocked": filtered out)

Comment: the tree does the heavy lifting (bounding and sorting, O(height + k)) and the fine filter comes afterward in Python, O(k). This is the architecture of any real query: the index shrinks the universe, the rest is filtered. Indexing every possible combination doesn't pay; you index the most selective dimension.

Solution 3

import random

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

def bst_height(tree):
    return node_height(tree.root)

keys = list(range(1023))
sorted_tree = build(keys)
shuffled_keys = keys[:]
random.shuffle(shuffled_keys)
random_tree = build(shuffled_keys)

print(bst_height(sorted_tree))   # 1022  (degenerate: one key per level)
print(bst_height(random_tree))   # ~20-24 (varies with the shuffle)

Comment: the minimum possible height with 1,023 = 2¹⁰ − 1 nodes is 9 (the perfect 10-level tree, 06-02's table). The random one comes out around ~20: not perfect, but still O(log n) — theory says the random BST averages ≈ 1.39·log₂ n... but no guarantee covers the sorted case, which gives 1022! Three numbers, three worlds: the ideal (9), the likely (≈20), and the catastrophic (1022). The next lesson guarantees staying one step from the ideal, no matter what arrives.

Conclusion

The BST has settled the outstanding accounts: with a single rule — smaller to the left, larger to the right — TaskFlow has an index that searches in O(height), lists in order via inorder (06-03's mystery, solved), finds minimum and successor at a glance, and answers ranges with pruning, including the "priority between 1 and 3" query that humbled the hash table, via the composite key (priority, id). You also know how to delete without breaking anything (leaf, one child, and the successor case) and you know the fine print of the contract: everything is O(height), and height depends on arrival order. With auto-incrementing ids — the daily bread — the BST degenerates into a list and its O(log n) evaporates, as you've just measured. The next lesson fixes this at the root: the AVL tree detects imbalance on every insertion with one number per node and corrects it with local rotations, guaranteeing O(log n) no matter what. TaskFlow's index is one lesson away from becoming indestructible.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved