Binary Search Trees

The previous lesson showed that traversing every node of a tree is $O(n)$. This is not good enough for search; linear search in an array has the same cost, and the tree provides no gain at all.

The gain appears once an ordering is added to the tree. If which branch to take at every node can be determined by a comparison, search traverses only a single path, not the whole tree.

The Ordering Invariant

A binary search tree is a binary tree that satisfies the following condition at every node:

Every value in the left subtree is smaller than the node’s value, and every value in the right subtree is larger.

The condition must hold for the entire subtree; looking only at the immediate children is not enough. This is an invariant in the sense defined in the Programming Fundamentals course: it must remain true before and after every operation.

            (12)
           /    \
        (7)      (25)
       /   \        \
    (3)    (10)     (30)

In this tree, every value in the subtree rooted at 25 is greater than $12$; every value in the subtree rooted at 7 is smaller. The same condition holds separately at every node.

The invariant has a direct consequence connected to the previous lesson: inorder traversal gives the values in ascending order. Because the left subtree is traversed first, then the node is visited, and finally the right subtree is traversed, the order arises on its own.

Search

Search starts at the root and makes a single comparison at every node:

• If the target value equals the node, it has been found.
• If it is smaller, descend into the left subtree; if larger, into the right subtree.
• If an empty link is reached, the value is not in the tree.

At every step, one of the subtrees is eliminated entirely. This is the tree counterpart of binary search on a sorted array, and its cost is proportional to height.

class BSTNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: "BSTNode | None" = None
        self.right: "BSTNode | None" = None


def search(root: BSTNode | None, target: int) -> tuple[bool, int]:
    """Searches for the target; returns (found, comparison count)."""
    steps = 0
    node = root
    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 insert(root: BSTNode | None, value: int) -> BSTNode:
    """Places the value in its position; returns the root. A duplicate is not inserted."""
    if root is None:
        return BSTNode(value)
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    return root


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


root = None
for value in (12, 7, 25, 3, 10, 30):
    root = insert(root, value)

print(inorder(root))        # [3, 7, 10, 12, 25, 30]  — sorted
print(search(root, 10))     # (True, 3)
print(search(root, 11))     # (False, 3)

The value 10 is found in three comparisons: 12 → 7 → 10. In this six-element tree, linear search would make six comparisons in the worst case.

Insertion

Insertion is a failed search: the position where the value should sit is searched for, and once an empty link is reached, the new node is attached there. The new node is always a leaf; no existing link changes.

This simplicity also preserves the ordering invariant on its own: since the node is placed at the end of the search path, it already satisfies the conditions of all its ancestor nodes.

What happens with duplicate values is a design decision: they can be ignored, placed in the right subtree, or tracked with a counter in the node. The implementation above chose the first option; if multiset behavior is wanted, the counter approach is suitable.

Deletion: Three Cases

Deletion is the most delicate operation on a tree; there are three cases depending on the number of children the deleted node has.

Leaf node. It is removed directly; the parent’s corresponding link is cleared.

Single-child node. The node is removed, and its one child is attached in its place. The entire subtree is effectively moved up; the ordering invariant is preserved.

Two-child node. It cannot be removed directly — two subtrees do not fit into one link. The solution is to replace the node’s value with its successor: the smallest value in the right subtree. This value can take its place because it is larger than the deleted node but smaller than every value in the right subtree. Since the successor node cannot have a left child, deleting it reduces to one of the first two cases.

def smallest(node: BSTNode) -> BSTNode:
    while node.left is not None:
        node = node.left
    return node


def delete(root: BSTNode | None, value: int) -> BSTNode | None:
    if root is None:
        return None
    if value < root.value:
        root.left = delete(root.left, value)
    elif value > root.value:
        root.right = delete(root.right, value)
    else:
        if root.left is None:                 # leaf or single child (right)
            return root.right
        if root.right is None:                # single child (left)
            return root.left
        succ = smallest(root.right)           # two children: replace with successor
        root.value = succ.value
        root.right = delete(root.right, succ.value)
    return root


root = None
for value in (12, 7, 25, 3, 10, 30):
    root = insert(root, value)

root = delete(root, 3)            # leaf
print(inorder(root))        # [7, 10, 12, 25, 30]

root = delete(root, 25)           # single child
print(inorder(root))        # [7, 10, 12, 30]

root = delete(root, 12)           # two children: the root
print(inorder(root))        # [7, 10, 30]

Inorder traversal staying sorted after every deletion is evidence that the invariant is preserved. This is the standard way to test a data structure’s correctness: checking the invariant after every operation.

The Degenerate Tree Problem

The promise of a binary search tree is that all operations are proportional to height. The value of that promise depends on the height being small — and there is no guarantee of that.

If values are inserted in ascending order, every new node attaches to the right; the tree turns into a linked list:

ascending = None
for value in (3, 7, 10, 12, 25, 30):        # sorted insertion
    ascending = insert(ascending, value)

mixed = None
for value in (12, 7, 25, 3, 10, 30):        # balanced order
    mixed = insert(mixed, value)

print(search(ascending, 30))        # (True, 6)  — every node was traversed
print(search(mixed, 30))            # (True, 3)

The same six values, the same structure, a twofold difference. When input arrives sorted — a situation frequently encountered in real data — the tree slips into its worst case.

This is the starting point of the next three lessons: keeping the tree’s height logarithmic regardless of insertion order.

Cost Table

Structure	Search	Insert	Delete	Sorted traversal
Hash table	$O(1)$ average	$O(1)$ average	$O(1)$ average	Not supported
Binary search tree (balanced)	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$
Binary search tree (degenerate)	$O(n)$	$O(n)$	$O(n)$	$O(n)$

Summary

• A binary search tree rests on the invariant that at every node the left subtree carries smaller values and the right subtree carries larger ones.
• As a consequence of the invariant, inorder traversal gives the values in ascending order.
• Search eliminates one subtree at every step; the cost is proportional to height.
• Insertion attaches a leaf at the end of a failed search; existing links do not change.
• Deletion has three cases; a two-child node is reduced to one of the first two cases by replacing it with the smallest value in its right subtree.
• There is no height guarantee: sorted input turns the tree into a linked list and all operations drop to linear.

Next Step

The problem has been defined: height depends on insertion order. The solution is to check the tree after every change and rearrange it when needed. The next lesson takes up the rotation operation that performs this rearrangement, and the two classic tree families that guarantee balance.