programmingconcepts

§ 2.5 · Data structures

Binary search trees

A tree where every node's left side holds smaller values and its right side holds larger ones, so a search can skip half the tree at each step.

A tree is a hierarchy of nodes: one root at the top, and every other node has exactly one parent. In a binary search tree, smaller values go left and larger values go right, so each comparison discards a whole subtree. Search, insert and delete take O(log n) when balanced, but O(n) when the tree degenerates into a line.

Find or insert
O(log n) if balanced
Worst case
O(n)
In-order walk
Sorted output
Duplicates
Ignored here
Requires
RecursionBinary search
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


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


def contains(root, value):
    while root is not None:
        if value == root.value:
            return True
        root = root.left if value < root.value else root.right
    return False

step 1 / 1comparingchangingfound

Fig. 2.5. Blue marks each node the search compares against; orange marks what changes. The stats line lists the values in order, which is always sorted.

Intuition

Binary search halves a sorted array at each step. A binary search tree builds that halving into the structure itself: each node is a “middle” that sends smaller values left and larger values right.

Unlike a sorted array, a tree can take new values without shifting anything. A new value just follows the comparisons down until it finds an empty spot.

How it works

  • Find: start at the root. If the value matches, stop. If it’s smaller, go left; if larger, go right. Reaching an empty spot means it isn’t there.
  • Insert: search for the value. The empty spot where the search ends is exactly where it belongs.
  • Delete has three cases:
    1. A leaf: just remove it.
    2. One child: that child’s subtree moves up into its place.
    3. Two children: copy in its successor (the smallest value in its right subtree), then delete the successor, which has at most one child.

Walking the tree left, node, right (an in-order walk) visits the values in sorted order.

Complexity

Every operation follows one path from the root, so its cost is the tree’s height. A balanced tree with n nodes is about log₂ n levels tall; 1,000,000 nodes need about 20 levels. But inserting already-sorted values builds a chain, n levels tall, and every operation becomes O(n). Self-balancing trees fix this by restructuring as they go.

Common mistakes

  1. Inserting sorted data into a plain BST. It degrades into a linked list. Shuffle first or use a balanced tree.
  2. Deleting a node with two children by removing it. Its subtrees would be lost. Replace it with its successor or predecessor.
  3. Checking only parent–child order. Every value in the whole left subtree must be smaller than the node, not just its left child.

In other languages

Language Sorted map or set in the standard library
Python None (the sortedcontainers package is popular)
JavaScript None
Java TreeMap, TreeSet (red-black trees)
C None
Go None
Rust BTreeMap, BTreeSet (B-trees: many values per node)

Check yourself

Check yourself

Insert 5, 3, 8, 1, 4 into an empty BST. What is the root's left child?

Check yourself

Insert 1, 2, 3, 4, 5 in that order. What shape is the tree?

Sources

  • Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 12, “Binary Search Trees” (3rd edition).
  • Donald Knuth, The Art of Computer Programming, Vol. 3, section 6.2.2.

Newsletter

One new concept each week, by email.

Signup opens soon.