Skip to content
LumenaryAcademy
Core 60 min

Trees and binary search trees

Hierarchies everywhere, sorted data kept sorted, and the difference between a tree of height 20 and one of height a million.

Code tested · 5AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

Hierarchies, and order that stays put

Trees are the shape of hierarchy, and hierarchy is everywhere in computing. The folders on your disk form a tree: one root, each folder containing files and further folders. A web page is a tree of elements (the DOM), a JSON document is a tree of objects and arrays, and before Python runs a line like total = (price + tax) * 4, it parses it into a tree in which * sits above + — you can see that tree yourself with the standard ast module. Organisation charts, family trees, the chapters and sections of a book, the moves of a game of chess: all trees.

Trees also solve a problem that hash tables cannot. A hash table answers "is this key here?" in expected constant time, but it scatters keys deliberately, so it cannot answer questions about order. A clinic's booking system needs "the first free appointment after 14:30"; a dictionary app needs "all words between kala and kalo"; a game server needs "the ten best scores". A sorted array answers these with binary search (from Searching and sorting), but inserting one new appointment shifts half the array. A binary search tree keeps keys in order and accepts insertions and deletions, each in time proportional to the tree's height. Whether that height is 20 or a million is the second half of the story.

DefinitionsH

Definitions

Definition— rooted tree

A rooted tree is either empty or consists of a root node together with zero or more subtrees, each itself a rooted tree, whose roots are the root's children. Every node except the root has exactly one parent. Nodes with no children are leaves; the others are internal nodes. Seen as a graph, a tree is connected and has no cycles (see graphs).

Definition— depth and height

The depth of a node is the number of edges on the path from the root to it; the root has depth 0. The height of a tree is the greatest depth of any node: a single node has height 0, and by convention the empty tree has height −1-1. (Some books count nodes instead of edges, which adds 1 to everything; always check the convention.)

Definition— binary tree

A binary tree is a rooted tree in which every node has at most two children, called its left and right child (either may be missing).

Definition— binary search tree

A binary search tree (BST) is a binary tree whose nodes hold keys from an ordered set, such that for every node xx: every key in xx's left subtree is less than xx's key, and every key in its right subtree is greater. (We assume distinct keys; a map stores a value alongside each key.)

4120651129509132depth 0depth 1depth 2depth 3
A binary search tree with eight keys and height 3. Everything left of 41 is smaller than 41, everything right of it is larger, and the same holds at every node, for whole subtrees, not just for children.
ExplanationH

Four ways to walk a tree

A traversal visits every node once. For a binary tree there are three natural recursive orders, named by when the node itself is visited relative to its two subtrees, plus one order that goes level by level.

OrderRuleOn the tree in the figure
Preordernode, then left subtree, then right subtree41 20 11 29 32 65 50 91
Inorderleft subtree, then node, then right subtree11 20 29 32 41 50 65 91
Postorderleft subtree, then right subtree, then node11 32 29 20 50 91 65 41
Level orderdepth 0, then depth 1, then depth 2, ...41 20 65 11 29 50 91 32

Each order has its uses:

  • Preorder sees a parent before its children, which is what you want for copying or saving a tree (the parent must exist before its children can be attached) and for printing an indented folder listing.
  • Inorder of a binary search tree produces the keys in sorted order, as we prove below.
  • Postorder sees all children before their parent, which is what you need whenever a node's answer depends on its children's answers: the disk usage of a folder (the du command), the value of an arithmetic expression, or freeing memory bottom-up.
  • Level order visits nodes in order of distance from the root. It uses a queue instead of recursion, and it is breadth-first search, which Graphs generalises.

Every traversal takes O(n)O(n) time, since each node is visited once and each edge followed once. The recursive versions use O(h)O(h) stack space, where hh is the height. That matters in Python, whose default recursion limit is about 1000: a recursive traversal of a tree a few thousand levels deep raises RecursionError, so production code often traverses with an explicit stack instead (see Recursion).

python
from collections import deque

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

#            41
#          /    \
#        20      65
#       /  \    /  \
#     11    29 50   91
#             \
#              32
root = Node(41, Node(20, Node(11), Node(29, None, Node(32))), Node(65, Node(50), Node(91)))

def preorder(t):
    return [] if t is None else [t.key] + preorder(t.left) + preorder(t.right)

def inorder(t):
    return [] if t is None else inorder(t.left) + [t.key] + inorder(t.right)

def postorder(t):
    return [] if t is None else postorder(t.left) + postorder(t.right) + [t.key]

def level_order(t):
    out, queue = [], deque([t] if t else [])
    while queue:
        node = queue.popleft()
        out.append(node.key)
        queue.extend(child for child in (node.left, node.right) if child)
    return out

def inorder_iterative(t):
    """Same output as inorder(), with an explicit stack instead of recursion."""
    out, stack = [], []
    while stack or t:
        while t:                    # go as far left as possible, remembering the way back
            stack.append(t)
            t = t.left
        t = stack.pop()             # the leftmost unvisited node
        out.append(t.key)
        t = t.right
    return out

for f in (preorder, inorder, postorder, level_order, inorder_iterative):
    print(f"{f.__name__:18}", f(root))

# Postorder in action: evaluate (7 - 2) * (3 + 1) from its expression tree.
expr = Node("*", Node("-", Node(7), Node(2)), Node("+", Node(3), Node(1)))
OPS = {"+": lambda a, b: a + b, "-": lambda a, b: a - b, "*": lambda a, b: a * b}

def evaluate(t):
    if t.left is None:                                       # a leaf holds a number
        return t.key
    return OPS[t.key](evaluate(t.left), evaluate(t.right))  # children first, then the node
print("(7 - 2) * (3 + 1) =", evaluate(expr))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

(The one-line list versions copy lists at every level, which makes them O(nh)O(n h) rather than O(n)O(n); they are written for clarity. A production traversal appends to one shared list or yields keys from a generator.)

ExplanationH

Binary search trees

The BST property turns every node into a signpost. To search for key kk, start at the root; if kk equals the node's key you are done, if it is smaller go left, if larger go right; if you fall off the tree, kk is not there. The argument is a loop invariant: if kk is anywhere in the tree, it is in the subtree rooted at the current node. It holds at the root, and each step preserves it because the BST property guarantees that all keys on the side we discard are on the wrong side of kk. Insertion is a search that, on falling off the tree, attaches a new leaf at the spot where the search ended. The minimum is found by going left until you cannot; the maximum, by going right.

Deletion has three cases. Let xx be the node holding the key to delete.

  1. xx is a leaf: remove it.
  2. xx has one child: let that child take xx's place.
  3. xx has two children: find its successor ss, the smallest key in xx's right subtree (go right once, then left as far as possible). Copy ss's key into xx, then delete ss from the right subtree. Since ss has no left child, that deletion is case 1 or 2. The BST property survives because ss is larger than everything in xx's left subtree and smaller than everything else in its right subtree.

Each operation walks one path from the root downward, so search, insertion, deletion, minimum, maximum and successor all take O(h)O(h) time.

Theorem— Inorder traversal sorts

An inorder traversal of a binary search tree visits its keys in increasing order.

Proof

By strong induction on the number of nodes nn. An empty tree produces the empty sequence, which is sorted. For a tree with root key rr, left subtree LL and right subtree RR, the traversal outputs inorder(LL), then rr, then inorder(RR). Both LL and RR are BSTs with fewer nodes, so by the induction hypothesis each output is sorted. Every key in LL is less than rr and every key in RR is greater than rr, by the BST property at the root. So the concatenation is sorted.

∎

The theorem gives a sorting algorithm for free (insert nn keys, then traverse), and it explains why a BST answers order questions: the keys between aa and bb are a contiguous stretch of the inorder sequence, and a range query can skip every subtree that lies entirely outside [a,b][a, b].

python
class BST:
    class _Node:
        __slots__ = ("key", "left", "right")
        def __init__(self, key):
            self.key, self.left, self.right = key, None, None

    def __init__(self):
        self.root = None

    def contains(self, key):
        node = self.root
        while node is not None:            # invariant: if key is in the tree, it is below `node`
            if key == node.key:
                return True
            node = node.left if key < node.key else node.right
        return False

    def insert(self, key):
        if self.root is None:
            self.root = self._Node(key)
            return
        node = self.root
        while True:
            if key == node.key:
                return                     # already present
            side = "left" if key < node.key else "right"
            child = getattr(node, side)
            if child is None:
                setattr(node, side, self._Node(key))
                return
            node = child

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

    def _delete(self, node, key):
        """Delete key from the subtree at node; return the subtree's new root."""
        if node is None:
            raise KeyError(key)
        if key < node.key:
            node.left = self._delete(node.left, key)
        elif key > node.key:
            node.right = self._delete(node.right, key)
        elif node.left is None:            # cases 1 and 2: at most one child
            return node.right
        elif node.right is None:
            return node.left
        else:                              # case 3: two children
            succ = node.right
            while succ.left is not None:
                succ = succ.left
            node.key = succ.key
            node.right = self._delete(node.right, succ.key)
        return node

    def inorder(self):
        out, stack, node = [], [], self.root
        while stack or node:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            out.append(node.key)
            node = node.right
        return out

t = BST()
for k in [41, 20, 65, 11, 29, 50, 91, 32]:
    t.insert(k)
print(t.inorder(), t.contains(32), t.contains(33))
t.delete(20)                               # two children: replaced by its successor, 29
print(t.inorder(), "root's left child is now", t.root.left.key)
t.delete(41)                               # the root itself: replaced by 50
print(t.inorder(), "new root:", t.root.key)
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
ExplanationH

Height is everything

Every BST operation costs O(h)O(h), so everything depends on how tall the tree is. A tree with nn nodes can be as tall as n−1n - 1 (a single path) or as short as about log⁡2n\log_2 n.

Theorem— How short a binary tree can be

A binary tree of height hh has at most 2h+1−12^{h+1} - 1 nodes. Hence a binary tree with nn nodes has height at least ⌈log⁡2(n+1)⌉−1\lceil \log_2(n+1) \rceil - 1.

Proof

Depth 0 holds one node, and each node has at most two children, so depth dd holds at most 2d2^d nodes (induction on dd). Summing over depths 00 to hh gives at most 1+2+⋯+2h=2h+1−11 + 2 + \cdots + 2^h = 2^{h+1} - 1 nodes. If n≤2h+1−1n \le 2^{h+1} - 1 then h+1≥log⁡2(n+1)h + 1 \ge \log_2(n+1), and since hh is an integer, h≥⌈log⁡2(n+1)⌉−1h \ge \lceil \log_2(n+1) \rceil - 1.

∎

A million keys therefore need a height of at least 19, and a well-shaped tree achieves about that. But the plain BST above does nothing to keep its shape. Insert keys in sorted order — exactly what happens when you load records that arrive by timestamp or by ID — and every new key becomes the right child of the previous one. The tree is a linked list, and every operation is O(n)O(n).

Random insertion orders are much kinder: the expected average depth of a node in a BST built from a random permutation is 2(1+1n)Hn−4≈2ln⁡n≈1.39log⁡2n2(1 + \frac{1}{n})H_n - 4 \approx 2 \ln n \approx 1.39 \log_2 n, where Hn=1+12+⋯+1nH_n = 1 + \frac12 + \cdots + \frac1n (the same count, for the same reason, as the expected comparisons of randomised quicksort), and the height is O(log⁡n)O(\log n) with high probability. But "random order" is an assumption about the input, and real inputs are often sorted, nearly sorted, or chosen by someone else.

python
import math, random

def build_and_measure(keys):
    """Insert keys into a plain BST (iteratively); return (height, average depth)."""
    left, right = {}, {}
    root = keys[0]
    depth = {root: 0}
    for k in keys[1:]:
        node = root
        while True:
            side = left if k < node else right
            if node in side:
                node = side[node]
            else:
                side[node] = k
                depth[k] = depth[node] + 1
                break
    return max(depth.values()), sum(depth.values()) / len(depth)

n = 2000
ordered = list(range(n))
shuffled = ordered[:]
random.Random(2026).shuffle(shuffled)
for label, keys in [("sorted insertion", ordered), ("random insertion", shuffled)]:
    h, avg = build_and_measure(keys)
    print(f"{label:17} height {h:5}   average depth {avg:7.1f}")
harmonic = sum(1 / i for i in range(1, n + 1))
print(f"lower bound on height: {math.ceil(math.log2(n + 1)) - 1}")
print(f"expected average depth for random order, 2(1 + 1/n)H_n - 4 = {2 * (1 + 1 / n) * harmonic - 4:.1f}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
ExplanationH

Balanced trees: AVL, red-black and B-trees

A balanced search tree guarantees height O(log⁡n)O(\log n) whatever the insertion order, by repairing its shape after every insertion and deletion. The repair tool is the rotation, a constant-time local rearrangement that changes heights but preserves the inorder sequence:

text
        y                         x
       / \     rotate right      / \
      x   C   ------------->    A   y
     / \      <-------------       / \
    A   B      rotate left        B   C

In both pictures the inorder sequence is A, x, B, y, C, so the BST property holds before and after; but the rotation moves subtree A up a level and C down one.

  • AVL trees (Georgy Adelson-Velsky and Evgenii Landis, 1962, the first balanced BSTs) require that at every node the heights of the two subtrees differ by at most 1. After an update, at most a few rotations along the path back to the root restore that rule. The height is at most about 1.44log⁡2n1.44 \log_2 n.
  • Red-black trees colour each node red or black, with rules that make every root-to-leaf path contain the same number of black nodes and forbid two reds in a row. Every path is therefore at most twice as long as the shortest, giving height at most 2log⁡2(n+1)2 \log_2(n + 1). They are a little less tightly balanced than AVL trees but need fewer rotations per update. Java's TreeMap is a red-black tree, C++'s std::map is one in the major standard libraries, and the Linux kernel has its own rbtree; its long-time CFS process scheduler kept runnable tasks in one, ordered by how much processor time each had received.
  • B-trees (Rudolf Bayer and Edward McCreight, 1972) are designed for data on disk or SSD, where reading one 4 or 8 KB page costs far more than any computation on it. A B-tree node fills a page, holding hundreds of sorted keys and pointers to hundreds of children, so the height is log⁡Bn\log_B n for a branching factor BB in the hundreds: three or four page reads find one row among billions. Nearly every relational database indexes with B-trees (SQLite, PostgreSQL, and others), as do many file systems; the lesson on databases returns to them.

Python's standard library has no balanced search tree. For ordered data it offers sorting, the bisect module for binary search on sorted lists, and heapq (next lesson) for "smallest so far". The popular third-party Sorted Containers library deliberately uses a list of sorted sublists instead of a tree, because contiguous lists are so cache-friendly in practice — a reminder that asymptotic analysis is where engineering starts, not where it ends. Redis takes yet another route for its sorted sets: a skip list, a randomised linked structure with expected O(log⁡n)O(\log n) operations.

Trees whose branching follows the characters of string keys, called tries, power autocomplete and IP routing tables; they appear in String algorithms.

Common misconceptionsH

Common misconceptions

Misconception

"A tree is a BST if every node is greater than its left child and less than its right child." The property is about whole subtrees. In the tree with root 10, left child 5, and 5's right child 12, every parent–child pair looks fine, but 12 sits in 10's left subtree, and a search for 12 starting at the root goes right and never finds it. A correct checker passes down the range of keys allowed at each node.

Misconception

"BST operations are O(log n)." They are O(h)O(h). That is O(log⁡n)O(\log n) only for balanced trees (or, on average, for random insertion orders). A plain BST fed sorted data has h=n−1h = n - 1.

Misconception

"Balanced means complete." A complete tree (every level full except possibly the last) is the most balanced shape possible, but keeping a tree complete under insertions would be expensive. Balanced trees accept a constant factor more height (1.44×1.44\times for AVL, 2×2\times for red-black) in exchange for cheap repairs. Heaps, in the next lesson, are complete trees, but they do not keep keys in search order.

Misconception

"Recursion is always fine for trees." For balanced trees the recursion depth is O(log⁡n)O(\log n), which is tiny. For an unbalanced tree built from sorted input it is nn, and Python raises RecursionError long before a million.

Exercises

Exercises

1. Trees and binary search trees

Warm-upHuman

Here is a binary search tree of letters:

          M
        /   \
       F     T
      / \     \
     B   H     W
              /
             V

Write its postorder traversal, as letters separated by spaces (for example A B C).

2. Trees and binary search trees

Warm-upHuman

Insert the keys 30,10,50,20,40,25,22,6030, 10, 50, 20, 40, 25, 22, 60, in that order, into an empty (plain, unbalanced) binary search tree. What is the height of the resulting tree? (Height counts edges: a single node has height 0.)

3. Trees and binary search trees

CoreHuman

In the BST from the lesson's figure (root 41; 20 with children 11 and 29; 29 with right child 32; 65 with children 50 and 91), you delete 41 using the successor method. Which key ends up at the root?

Choose one

4. Trees and binary search trees

CoreHuman

What is the smallest possible height of a binary tree with 1000 nodes? (Height counts edges.)

5. Trees and binary search trees

CoreComputational

Write is_bst(root) that returns True exactly when the binary tree rooted at root is a valid binary search tree with distinct keys: for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. The empty tree (None) is a valid BST.

Beware the trap from the misconceptions: checking each node only against its own children is not enough. Your function should run in O(n)O(n) time.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

6. Trees and binary search trees

CoreComputational

A clinic stores appointment times (minutes after midnight) as keys in a binary search tree. Write keys_between(root, lo, hi) that returns a sorted list of all keys kk with lo≤k≤hilo \le k \le hi.

Do not traverse the whole tree: skip every subtree that cannot contain keys in the range. With that pruning the running time is O(h+k)O(h + k), where kk is the number of keys reported.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Trees and binary search trees

CoreHuman

A database index on a table of a billion rows lives mostly on SSD. Why do databases use B-trees with hundreds of keys per node, rather than red-black trees with one key per node?

Choose one

Further reading and resources