Binary Search Trees

AQA 4.2.8 — Binary search trees

Retrieval: the previous lesson's worked tree — built from the values 8, 3, 10, 1, 6, 14, 4, 7, 13 — traversed in-order to a fully sorted sequence. That wasn't luck: that tree satisfies a special extra property, the Binary Search Tree (BST) property.

Key vocabulary

• BST property — for every node, every value in its left subtree is smaller than the node's own value, and every value in its right subtree is larger.
• Insertion — adding a new value to a BST while preserving the BST property.
• Balanced / unbalanced tree — whether a tree's shape keeps its height close to the minimum possible for its number of nodes, or lets it grow much taller than necessary.

Understand — why the BST property enables fast search

Because every node's left subtree is guaranteed smaller and its right subtree guaranteed larger, a single comparison at each node tells you which entire subtree could possibly contain your target — and lets you discard the other subtree completely, without even looking inside it.

Connecting to Year 12, precisely: Sequence 5's binary search eliminated half of a sorted array at each step by jumping to a calculated middle index. BST search uses the same core strategic idea — eliminate half of the remaining possibilities at every comparison — but the mechanism is genuinely different: there is no array, no index arithmetic, and no requirement that the data was pre-sorted into contiguous memory. Instead, the tree's own shape, built up through insertion, already encodes the ordering via explicit left/right links. The two are not the same technique — a BST can be searched even while it's actively being built and changed, something a static sorted array cannot do without an expensive re-sort — but they share the same underlying "compare and discard half" logic, which is why BST search averages the same O(log n) performance as binary search, provided the tree stays reasonably balanced (see Analyse, below).

See it — building the tree via insertion

Inserting 8, 3, 10, 1, 6, 14, 4, 7, 13 one at a time, in that order, recreates the exact tree from the previous lesson: 8 becomes the root; 3 < 8, so it goes left of 8; 10 > 8, so it goes right of 8; 1 < 8, then 1 < 3, so it goes left of 3; and so on, each new value following the BST property down from the root until it finds an empty spot.

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

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
            return
        self._insert_at(self.root, value)

    def _insert_at(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert_at(node.left, value)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert_at(node.right, value)

    def search(self, value):
        return self._search_at(self.root, value)

    def _search_at(self, node, value):
        if node is None:
            return False
        if node.value == value:
            return True
        elif value < node.value:
            return self._search_at(node.left, value)
        else:
            return self._search_at(node.right, value)

Trace it — inserting 15, 6, 23

Into an empty tree: insert 15 → becomes the root. Insert 6 → 6 < 15, root's left is empty, so 6 becomes 15's left child. Insert 23 → 23 > 15, root's right is empty, so 23 becomes 15's right child. Each insertion follows exactly one comparison-guided path down from the root until it reaches an empty link.

Debug it — diagnose, explain, fix, test, justify (incorrect tree links)

def _insert_at(self, node, value):
    if value < node.value:
        if node.left is None:
            Node(value)
        else:
            self._insert_at(node.left, value)
    else:
        if node.right is None:
            node.right = Node(value)
        else:
            self._insert_at(node.right, value)

Calling insert(value) for a value that should go left of some node appears to succeed with no error at all — but search() for that value later returns False.

1. Diagnose: does Node(value) on its own line actually connect the new node to the tree anywhere?
2. Explain: what happens to an object that's created but never assigned to an attribute?
3. Fix: correct the line so the new node is genuinely linked in.
4. Test: confirm search() now correctly finds a value inserted down the left side of the tree.
5. Justify: explain why this bug is more dangerous than one that raises an exception.

(Node(value) creates the object but never assigns it to node.left, so Python discards it immediately - nothing references it, exactly the "local variable vs. attribute" mistake from Sequence 11, now applied to a tree LINK instead of an object's own state. The fix is node.left = Node(value). This is more dangerous than a crashing bug because the program appears to run successfully - insert() returns normally, giving no indication that the value was silently lost.)

Analyse — best case, worst case

Search and insertion average O(log n) for a "bushy," reasonably balanced tree, where each comparison genuinely halves the remaining search space. But the worst case is O(n) if the tree becomes a degenerate chain — for example, inserting 1, 2, 3, 4, 5 in already-sorted order: each new value is larger than every existing node, so it always becomes the rightmost node's right child, producing a tree that is really just a linked list wearing a tree's clothing, with height 4 for only 5 nodes (compare a bushy 5-node tree, which can have height as low as 2). The O(log n) claim above depends entirely on the tree staying reasonably balanced — insertion order matters.

Compare, select, justify

A programmer needs to store a fixed set of about 1000 unique product IDs, loaded once and never changed afterwards, and repeatedly check whether a given ID exists. Would a BST or a plain sorted array with binary search be more appropriate? Justify your answer.

(A sorted array with binary search. Since the data never changes after loading, a BST's main advantage — efficient insertion and deletion without a full re-sort — is never actually used. Binary search on a sorted array instead offers a guaranteed O(log n) worst case (no risk of the tree degenerating), lower memory overhead (no left/right pointers stored per item), and a simpler implementation.)

Common mistake

Assuming a BST always guarantees O(log n) performance "because it's a tree, so it's automatically fast." The Analyse section above shows this is false for a poorly balanced tree — the guarantee depends on the tree's actual shape, not merely on it being a tree at all.

Why this matters for the NEA

Choosing between structures with genuinely different guarantees — a BST's flexibility under change versus an array's guaranteed worst case — is precisely the kind of justified design decision AQA's NEA marking rewards. It's the reasoning behind the choice that matters, not which specific structure gets picked.

Check your understanding

Insert the values 15, 6, 23, 4, 12, 71 into an empty BST, in that order. Describe the resulting tree's parent/child structure, and state its height. (4 marks)

(15 is the root. 6 < 15 becomes its left child; 23 > 15 becomes its right child. 4 < 15 then < 6 becomes 6's left child; 12 < 15 then > 6 becomes 6's right child. 71 > 15 then > 23 becomes 23's right child. Height: 2 (the longest path, root → 6 → 4 or root → 6 → 12 or root → 23 → 71, has 2 edges).)

Challenge

Add a method find_min() that returns the smallest value in the BST without checking every node — using the BST property to go directly to it (hint: the smallest value is always found by following left links as far as possible from the root).

Looking ahead: the next lesson covers hash tables — a completely different strategy for fast lookup, aiming for O(1) rather than O(log n), by computing where a key belongs rather than comparing to find it.