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.
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 . (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 : every key in 's left subtree is less than 's key, and every key in its right subtree is greater. (We assume distinct keys; a map stores a value alongside each key.)
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.
| Order | Rule | On the tree in the figure |
|---|---|---|
| Preorder | node, then left subtree, then right subtree | 41 20 11 29 32 65 50 91 |
| Inorder | left subtree, then node, then right subtree | 11 20 29 32 41 50 65 91 |
| Postorder | left subtree, then right subtree, then node | 11 32 29 20 50 91 65 41 |
| Level order | depth 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
ducommand), 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 time, since each node is visited once and each edge followed once. The recursive versions use stack space, where 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).
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))(The one-line list versions copy lists at every level, which makes them rather than ; they are written for clarity. A production traversal appends to one shared list or yields keys from a generator.)
Binary search trees
The BST property turns every node into a signpost. To search for key , start at the root; if equals the node's key you are done, if it is smaller go left, if larger go right; if you fall off the tree, is not there. The argument is a loop invariant: if 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 . 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 be the node holding the key to delete.
- is a leaf: remove it.
- has one child: let that child take 's place.
- has two children: find its successor , the smallest key in 's right subtree (go right once, then left as far as possible). Copy 's key into , then delete from the right subtree. Since has no left child, that deletion is case 1 or 2. The BST property survives because is larger than everything in '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 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 . An empty tree produces the empty sequence, which is sorted. For a tree with root key , left subtree and right subtree , the traversal outputs inorder(), then , then inorder(). Both and are BSTs with fewer nodes, so by the induction hypothesis each output is sorted. Every key in is less than and every key in is greater than , by the BST property at the root. So the concatenation is sorted.
∎
The theorem gives a sorting algorithm for free (insert keys, then traverse), and it explains why a BST answers order questions: the keys between and are a contiguous stretch of the inorder sequence, and a range query can skip every subtree that lies entirely outside .
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)Height is everything
Every BST operation costs , so everything depends on how tall the tree is. A tree with nodes can be as tall as (a single path) or as short as about .
Theorem— How short a binary tree can be
A binary tree of height has at most nodes. Hence a binary tree with nodes has height at least .
Proof
Depth 0 holds one node, and each node has at most two children, so depth holds at most nodes (induction on ). Summing over depths to gives at most nodes. If then , and since is an integer, .
∎
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 .
Random insertion orders are much kinder: the expected average depth of a node in a BST built from a random permutation is , where (the same count, for the same reason, as the expected comparisons of randomised quicksort), and the height is 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.
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}")Balanced trees: AVL, red-black and B-trees
A balanced search tree guarantees height 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:
y x
/ \ rotate right / \
x C -------------> A y
/ \ <------------- / \
A B rotate left B CIn 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 .
- 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 . They are a little less tightly balanced than AVL trees but need fewer rotations per update. Java's
TreeMapis a red-black tree, C++'sstd::mapis 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 for a branching factor 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 operations.
Trees whose branching follows the characters of string keys, called tries, power autocomplete and IP routing tables; they appear in String algorithms.
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 . That is only for balanced trees (or, on average, for random insertion orders). A plain BST fed sorted data has .
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 ( for AVL, 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 , which is tiny. For an unbalanced tree built from sorted input it is , and Python raises RecursionError long before a million.
Exercises
1. Trees and binary search trees
Warm-upHumanHere 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-upHumanInsert the keys , 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
CoreHumanIn 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?
4. Trees and binary search trees
CoreHumanWhat is the smallest possible height of a binary tree with 1000 nodes? (Height counts edges.)
5. Trees and binary search trees
CoreComputationalWrite 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 time.
6. Trees and binary search trees
CoreComputationalA 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 with .
Do not traverse the whole tree: skip every subtree that cannot contain keys in the range. With that pruning the running time is , where is the number of keys reported.
7. Trees and binary search trees
CoreHumanA 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?
Further reading and resources
- Organization and maintenance of large ordered indexes · Rudolf Bayer and Edward M. McCreight · 1972The paper that introduced B-trees, the index structure inside nearly every database.
- A dichromatic framework for balanced trees · Leonidas J. Guibas and Robert Sedgewick · 1978Where red-black trees got their name and their now-standard presentation.
- Red-black Trees (rbtree) in Linux · The Linux kernel documentation
- SQLite Database File FormatDescribes the B-tree pages in which SQLite stores every table and every index.
- PostgreSQL: B-Tree Indexes
- Python Sorted Containers · Grant JenksThe most widely used sorted collection for Python, with a fascinating explanation of why it is not built on a tree.
- ast — Abstract Syntax Trees · Python documentation
- Open Data Structures · Pat MorinFree chapters on binary search trees, treaps, scapegoat trees, red-black trees and B-trees.