Binary Search Trees

Add one ordering rule to a binary tree and get fast search, insertion, and deletion, as long as the tree stays balanced

Introduction

Lesson 7's binary tree had no rule for where values go, so finding one meant checking every node, O(n), no better than a linked list. A binary search tree (BST) adds a single ordering invariant: for every node, everything in its left subtree is smaller, and everything in its right subtree is larger. That one rule is enough to turn search, insert, and delete into O(h) operations, where h is the tree's height, which combines an array's fast search with a linked list's fast insert and delete.

The BST Invariant

A Valid Binary Search Tree

5381479

Figure 1: Every left descendant is smaller, every right descendant is larger, at every node

This isn't just true for a node and its immediate children, it holds recursively, for every node and its entire left or right subtree. 4 is smaller than 5 even though it's two levels down, because it lives inside 5's left subtree the whole way.

Searching and Inserting

The ordering invariant tells you exactly which direction to go at every step: smaller than the current node, go left, larger, go right. That's true whether you're searching for a value or deciding where a new one belongs.

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

    def insert(self, value: int) -> None:
        self.root = self._insert(self.root, value)

    def _insert(self, node: "TreeNode | None", value: int) -> "TreeNode":
        if node is None:
            return TreeNode(value)
        if value < node.value:
            node.left = self._insert(node.left, value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        # else: value already exists, this implementation stores no duplicates
        return node

    def search(self, value: int) -> bool:
        return self._search(self.root, value)

    def _search(self, node: "TreeNode | None", value: int) -> bool:
        if node is None:
            return False
        if value == node.value:
            return True
        if value < node.value:
            return self._search(node.left, value)
        return self._search(node.right, value)
bst = BST()
for value in [5, 3, 8, 1, 4, 7, 9]:
    bst.insert(value)

print(bst.search(4))
print(bst.search(6))
Expected Output:
True
False
Why O(h) Instead of O(n)

Every comparison eliminates an entire subtree from consideration, exactly like Lesson 1's binary search. The number of comparisons needed is bounded by the tree's height, not its size, which is the whole reason BSTs are worth the extra bookkeeping over a plain list.

In-order Traversal Gives You Sorted Order, for Free

Lesson 7's inorder traversal (left, root, right) visits a BST's values in ascending order, no extra work required. The same ordering rule that makes search fast also makes sorted output fall out automatically.

def inorder(node: "TreeNode | None") -> list[int]:
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

print(inorder(bst.root))
Expected Output:
[1, 3, 4, 5, 7, 8, 9]

Deletion: The Tricky One

Deleting a node has to preserve the ordering invariant for everything left behind, and that splits into three cases:

No childrenJust remove the node, nothing to reconnect
One childThe node's parent adopts that single child directly
Two childrenReplace the value with its in-order successor, then delete that successor
def delete(node: "TreeNode | None", value: int) -> "TreeNode | None":
    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 the node to delete
        if node.left is None:
            return node.right          # 0 or 1 child: just splice it out
        if node.right is None:
            return node.left           # 1 child: just splice it out

        # 2 children: find the in-order successor, the smallest value in the
        # right subtree, copy its value up, then delete that successor instead
        successor = node.right
        while successor.left is not None:
            successor = successor.left
        node.value = successor.value
        node.right = delete(node.right, successor.value)

    return node
root = bst.root
root = delete(root, 1)        # leaf: no children
print(inorder(root))

root = delete(root, 3)        # one child left after the previous delete
print(inorder(root))

root = delete(root, 8)        # two children: replaced by its successor, 9
print(inorder(root))
Expected Output:
[3, 4, 5, 7, 8, 9]
[4, 5, 7, 8, 9]
[4, 5, 7, 9]

The two-children case is the one worth seeing. In the delete(root, 8) call above, 8 has both a left child (7) and a right child (9). Its in-order successor, the smallest value in its right subtree, is 9. That value is copied up into 8's spot, and the original 9 is then removed from below:

Before: delete(8)

54879

After: 9 replaces 8

5497

Figure 2: The successor 9 (amber) is promoted into the deleted node's position, and the original 9 leaf is unlinked. Every value in the left subtree is still smaller, every value in the right subtree still larger, so the ordering invariant holds.

The in-order successor of a node is the smallest value in its right subtree, found by walking as far left as possible from there. It's guaranteed to have no left child itself, which is exactly what keeps the two-children case from spiraling into more special cases.

Balancing Intuition

O(h) is only fast if h stays close to log₂(n). Nothing in the insert logic above guarantees that. Insert already-sorted data, and every new value is larger than everything before it, so it always becomes the new rightmost node:

def height(node: "TreeNode | None") -> int:
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

degenerate = BST()
for value in [1, 2, 3, 4, 5]:      # already sorted input
    degenerate.insert(value)

print(height(degenerate.root))     # 4, a straight line, not a tree in spirit
Expected Output:
4

A height of 4 for only 5 nodes means every operation degrades to O(n), the BST has quietly become a linked list wearing a tree's syntax. A well-balanced 5-node tree has a height of just 2.

Note: Fixing this is the job of self-balancing BST variants, AVL trees and red-black trees are the classic examples, which detect when an insertion or deletion has unbalanced the tree and perform local rotations to restore a bounded height. The invariant and the O(h) reasoning in this lesson still apply directly to them, they just add machinery to guarantee h never drifts far from log₂(n).

Bonus: Validating a Binary Search Tree

A common trap: checking only that each node is larger than its left child and smaller than its right child isn't enough. A node can satisfy that local check while still violating the invariant of an ancestor further up. The fix is to carry a valid range down through the recursion instead of only comparing parent and child directly:

def is_valid_bst(
    node: "TreeNode | None",
    lower: int | None = None,
    upper: int | None = None,
) -> bool:
    if node is None:
        return True
    if lower is not None and node.value <= lower:
        return False
    if upper is not None and node.value >= upper:
        return False
    # Every node in the left subtree must stay below "node.value", every node
    # in the right subtree must stay above it, no matter how deep it is
    return (
        is_valid_bst(node.left, lower, node.value)
        and is_valid_bst(node.right, node.value, upper)
    )
print(is_valid_bst(bst.root))

# A tree that looks fine one level at a time, but breaks the global rule:
# 2 sits in 5's right subtree, so it must be greater than 5, but it isn't
sneaky_root = TreeNode(5)
sneaky_root.left = TreeNode(3)
sneaky_root.right = TreeNode(8)
sneaky_root.right.left = TreeNode(2)
sneaky_root.right.right = TreeNode(9)

print(is_valid_bst(sneaky_root))
Expected Output:
True
False

In sneaky_root, the node 2 is smaller than its immediate parent 8, so a naive local check would accept it, but it sits inside 5's right subtree, where every value must be greater than 5. Tracking the running lower/upper bounds is what catches it.

Key Takeaways

  • The BST invariant is recursive - left subtree smaller, right subtree larger, at every node, not just immediate children
  • Search, insert, and delete are all O(h), where h is the tree's height, not the number of nodes
  • In-order traversal always yields sorted output, a direct consequence of the ordering invariant
  • Deleting a two-children node works by swapping in its in-order successor, then deleting that simpler node instead
  • An unbalanced BST degrades to O(n), sorted input is the worst case; self-balancing variants exist specifically to prevent this
Data Structures & AlgorithmsLesson 8