9. Trees

A tree is a connected graph with no cycles: the most economical way to connect a set of vertices, with exactly one route between any two of them. Trees model every hierarchy (file systems, organization charts, the DOM, parse trees) and every branching process (comparisons, decisions, game moves), and they are the skeleton of the most important data structures and network-design algorithms. This chapter characterizes trees and counts them, applies them to searching, compression and games, shows how to traverse them systematically, and builds spanning trees and minimum spanning trees of graphs.

<a id="91-tree-fundamentals"></a>

9.1 Tree Fundamentals

This subchapter defines trees, proves the equivalent characterizations that make them easy to recognize, introduces rooted and m-ary trees with their vocabulary and counting formulas, relates height to balance, and counts labeled trees.

Properties of Trees

Why. Suppose you must connect n offices with network links. You want every office to reach every other one, but every extra link costs money. If a link lies on a cycle, you can remove it and everything stays connected (8.3), so a cheapest connected network has no cycles at all. Such a network is a tree. Trees are the minimal connected graphs, and that single idea can be stated in half a dozen equivalent ways. In practice, you check whichever one is easiest.

What. A tree is a connected undirected graph with no cycles. A forest is a graph with no cycles: each of its connected components is a tree. A vertex of degree 1 in a tree is a leaf, and a vertex of degree at least 2 is an internal vertex.

Characterization theorem. For a simple graph G with n vertices, the following statements are equivalent:

	Statement	Viewpoint
1	G is connected and acyclic	The definition
2	Every two vertices are joined by exactly one simple path	Unique routes
3	G is connected and has n − 1 edges	Counting, with connectivity
4	G is acyclic and has n − 1 edges	Counting, with acyclicity
5	G is connected, and removing any edge disconnects it	Minimally connected: every edge is a bridge (8.3)
6	G is acyclic, and adding any new edge creates exactly one cycle	Maximally acyclic

Proof sketches.

• Leaf lemma. Every tree with n ≥ 2 vertices has at least two leaves. Proof. Take a longest path v₀, v₁, …, v_k. If v₀ had a neighbor other than v₁, that neighbor would either be on the path, closing a cycle, or off the path, giving a longer path. So v₀ is a leaf, and so is v_k by the same argument.
• A tree has n − 1 edges (1 ⇒ 3). Induction on n. A single vertex has 0 edges. For n ≥ 2, remove a leaf and its only edge. What is left is still connected and acyclic, so it is a tree with n − 1 vertices and, by the induction hypothesis, n − 2 edges. Adding the leaf back gives n − 1 edges.
• 1 ⇔ 2. If two different simple paths joined u and v, then following one path out and the other path back would contain a cycle. Conversely, if G had a cycle, any two vertices on it would be joined by two different paths, one around each side.
• 3 ⇒ 1. If a connected graph with n − 1 edges had a cycle, removing a cycle edge would keep it connected. Repeating this would end with a tree that has fewer than n − 1 edges, contradicting 1 ⇒ 3.
• 4 ⇒ 1. Each component of a forest is a tree, so a forest with c components has n − c edges. With n − 1 edges, c = 1.
• 1 ⇔ 5 and 1 ⇔ 6. An edge is a bridge exactly when it lies on no cycle (8.3). Adding the edge {u, v} to a tree creates the cycle formed by that edge and the unique u–v path, and no other cycle.

Useful consequences.

• A forest with n vertices and c components has exactly n − c edges.
• By the handshaking lemma (8.1), the degrees of a tree add up to 2(n − 1), so the average degree is below 2.
• Counting leaves. Σ (deg(v) − 2) = 2(n − 1) − 2n = −2. Each leaf contributes −1 to this sum and each degree-2 vertex contributes 0, so

  number of leaves = 2 + Σ_{deg(v) ≥ 3} (deg(v) − 2)

A tree with no vertex of degree 3 or more is a path, which has exactly 2 leaves. Each extra branch adds leaves.

• In a tree, every edge is a bridge and every non-leaf vertex is a cut vertex (8.3).

Analogy. A tree is a road network with no detours. There is exactly one way to drive between any two towns. Close any road and some towns are cut off. Build any new road and you create a loop.

Example.

            0
          ╱ │ ╲
         1  2  3            n = 7, m = 6 = n − 1
        ╱ ╲     │           degrees: 0:3  1:3  2:1  3:2  4:1  5:1  6:1
       4   5    6           leaves {2, 4, 5, 6}: 2 + (3 − 2) + (3 − 2) = 4

def is_tree(n, edges):
    if len(edges) != n - 1:                  # characterization 3: n − 1 edges ...
        return False
    adj = {v: [] for v in range(n)}
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    seen, stack = {0}, [0]
    while stack:                             # ... and connected: DFS from vertex 0 reaches everything
        u = stack.pop()
        for w in adj[u]:
            if w not in seen:
                seen.add(w)
                stack.append(w)
    return len(seen) == n

T = [(0, 1), (0, 2), (0, 3), (1, 4), (1, 5), (3, 6)]
print(is_tree(7, T))                         # True
print(is_tree(7, T + [(4, 5)]))              # False: 7 edges, so a cycle was created
two_parts = [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 6)]
print(is_tree(7, two_parts))                 # False: n − 1 edges, but a cycle and two components

deg = [sum(v in e for e in T) for v in range(7)]
print(deg.count(1), 2 + sum(d - 2 for d in deg if d >= 3))   # 4 4   the leaf-count formula

Key takeaways

• A tree is a connected acyclic graph. A forest is an acyclic graph whose components are trees.
• Any two of "connected", "acyclic" and "n − 1 edges" imply the third.
• Trees have unique paths, every edge is a bridge, and adding any edge creates exactly one cycle.
• Every tree with at least 2 vertices has at least 2 leaves, and the number of leaves is 2 + Σ_{deg ≥ 3} (deg(v) − 2).
• Edge count alone is not enough: n − 1 edges can still form a disconnected graph with a cycle.

Practice

1. (Beginner) A tree has two vertices of degree 4, one vertex of degree 3, and all its other vertices are leaves. How many leaves does it have, and how many vertices in total?
2. (Intermediate) Prove that a forest with n vertices and c components has n − c edges. Then show that a graph with n vertices, c components and m edges contains at least m − n + c cycles. Hint: every edge beyond a spanning forest closes a different cycle (characterization 6).
3. (Interview) Graph valid tree. Given n and a list of undirected edges, decide whether they form a tree, in near-linear time and without building an adjacency list. Hint: first check that there are exactly n − 1 edges. Then process the edges with union–find (8.3) and fail as soon as an edge joins two vertices that are already connected.

Rooted Trees

Why. Many trees come with a natural top: the root directory of a file system, the CEO of a company, the <html> element of a web page, the current position in a game. Choosing a root orients every edge away from it, and gives meaning to words like parent, child and ancestor. It also makes trees recursive: a rooted tree is a root together with the rooted subtrees hanging from its children, and almost every algorithm on trees follows that recursion.

What. A rooted tree is a tree with one designated vertex, the root, and every edge directed away from the root. Since paths in a tree are unique, each vertex v ≠ root has exactly one parent: the next vertex on the path from v to the root.

Term	Meaning
Parent of v	The neighbor of v on the path from v to the root
Child of v	A vertex whose parent is v
Siblings	Vertices with the same parent
Ancestors of v	The vertices on the path from the parent of v up to the root
Descendants of v	The vertices that have v as an ancestor
Leaf	A vertex with no children
Internal vertex	A vertex with at least one child (the root is internal unless it is the only vertex)
Subtree rooted at v	v together with all its descendants and the edges between them
Level (depth) of v	The length of the path from the root to v. The root is at level 0
Height	The maximum level of any vertex

An ordered rooted tree also fixes a left-to-right order of the children of every vertex. Ordered trees are needed whenever the order of children matters: the arguments of a function call, the statements of a block, the left and right subtrees of a binary tree.

Any vertex of an unrooted tree can be chosen as the root. A BFS from the chosen root (8.4) sets every parent pointer in O(n) time.

Representations.

Representation	Stores	Good for
Parent array	parent[v] for each vertex	Walking up: ancestors, depth, union–find
Child lists	children[v] for each vertex	Walking down: traversals, subtree computations
Left-child, right-sibling	Two pointers per vertex: the first child and the next sibling	Storing any ordered tree as a binary tree

Analogy. A rooted tree is a family tree read from one ancestor downward: every person except that ancestor has exactly one parent in the picture, and a person's descendants form a smaller family tree of their own.

Example: a file system.

                 /                       level 0   root
             ╱   │    ╲
          etc   home   usr               level 1
           │    ╱  ╲     │
        hosts ana  ben  bin              level 2
               │
            notes.md                     level 3   height = 3

parent = {"/": None, "etc": "/", "home": "/", "usr": "/", "hosts": "etc",
          "ana": "home", "ben": "home", "bin": "usr", "notes.md": "ana"}

children = {v: [] for v in parent}
for v, p in parent.items():
    if p is not None:
        children[p].append(v)                     # invert the parent array into child lists

def depth(v):
    return 0 if parent[v] is None else 1 + depth(parent[v])

def ancestors(v):
    out = []
    while parent[v] is not None:
        v = parent[v]
        out.append(v)
    return out

def subtree_size(v):
    return 1 + sum(subtree_size(c) for c in children[v])

print(children["home"])                           # ['ana', 'ben']
print(depth("notes.md"), ancestors("notes.md"))   # 3 ['ana', 'home', '/']
print(subtree_size("home"))                       # 4   home, ana, ben, notes.md
print([v for v in parent if not children[v]])     # ['hosts', 'ben', 'bin', 'notes.md']   the leaves
print(max(depth(v) for v in parent))              # 3   the height

Key takeaways

• Rooting a tree directs every edge away from the root, and every non-root vertex gets exactly one parent.
• Level is the distance from the root. Height is the maximum level.
• Each vertex is the root of its own subtree, so rooted trees are naturally recursive.
• Parent arrays make it easy to walk up, child lists make it easy to walk down, and the left-child, right-sibling form turns any ordered tree into a binary tree.

Practice

1. (Beginner) In the file-system tree, list the siblings of home, the descendants of home, the ancestors of bin, and all internal vertices. What changes in the levels and in the height if the tree is re-rooted at ana?
2. (Intermediate) Draw the left-child, right-sibling representation of the file-system tree. Explain why every ordered tree with n vertices becomes a binary tree with n vertices whose root has no right child.
3. (Interview) Lowest common ancestor. Each node of a tree stores only a pointer to its parent. Find the deepest node that is an ancestor of both u and v, using O(1) extra memory. Hint: compute both depths, move the deeper node up until both are at the same depth, then move both up together until they meet. For many queries on a fixed tree, read about binary lifting.

M-ary Trees

Why. Many trees limit how many children a vertex can have: binary search trees (2), ternary decisions such as a balance scale (3), quadtrees in graphics (4), and B-tree indexes in databases, whose nodes can have hundreds of children. Once the branching factor is fixed, the numbers of vertices, internal vertices and leaves are tied together by exact formulas. These formulas answer counting questions, such as how many matches a tournament needs, without drawing anything.

What. A rooted tree is m-ary if every internal vertex has at most m children, and full m-ary if every internal vertex has exactly m children. A 2-ary tree is a binary tree. In an ordered binary tree, the two children are called the left child and the right child.

The word "complete" has two meanings in the literature:

Term	Meaning
Full m-ary	Every internal vertex has exactly m children
Perfect m-ary (also called complete in some discrete-math texts)	Full, with all leaves on the same level
Complete binary tree (data-structures sense)	Every level is full except possibly the last, which is filled from left to right. This is the shape of a binary heap

Theorem. A full m-ary tree with i internal vertices has n = m·i + 1 vertices.

Proof. Every vertex except the root is the child of exactly one internal vertex, and each internal vertex has m children. So there are m·i non-root vertices, plus the root.

Combined with n = i + l (every vertex is internal or a leaf), knowing any one of n, i or l determines the other two:

Given	Vertices n	Internal vertices i	Leaves l
n	n	(n − 1)/m	((m − 1)n + 1)/m
i	m·i + 1	i	(m − 1)i + 1
l	(m·l − 1)/(m − 1)	(l − 1)/(m − 1)	l

Example 1: a tournament. In a single-elimination tournament with 64 players, the matches are the internal vertices of a full binary tree whose leaves are the players. So there are i = (l − 1)/(m − 1) = 63 matches. More directly, every match eliminates exactly one player, and 63 players must be eliminated.

Example 2: a chain letter. Each person who receives a letter either forwards it to exactly 4 new people or does not forward it at all. If 100 people received it and did not forward it, the spread is a full 4-ary tree with l = 100 leaves. So i = 99/3 = 33 people forwarded it and n = (4·100 − 1)/3 = 133 people saw it, including the person who started it.

Leaves and height. An m-ary tree of height h has at most m^h leaves and at most (m^{h+1} − 1)/(m − 1) vertices, because level k holds at most m^k vertices. So a tree with l leaves has height at least ⌈log_m l⌉. This one inequality gives the lower bounds for searching and sorting (decision trees, 9.2).

How: storing an m-ary tree in an array. Number the vertices level by level, from left to right, starting at 0. The children of vertex k are then m·k + 1, …, m·k + m, and its parent is ⌊(k − 1)/m⌋. No pointers are needed. Binary heaps (m = 2) use exactly this layout.

import random

def grow_full_tree(m, expansions, seed=1):
    """Start from a single leaf and, repeatedly, give a random leaf m children."""
    rng = random.Random(seed)
    children, leaves = {0: []}, [0]
    for _ in range(expansions):
        v = leaves.pop(rng.randrange(len(leaves)))      # this leaf becomes an internal vertex
        kids = list(range(len(children), len(children) + m))
        children[v] = kids
        for k in kids:
            children[k] = []
        leaves += kids
    return children

for m in (2, 3, 5):
    t = grow_full_tree(m, expansions=10)
    n = len(t)
    i = sum(1 for kids in t.values() if kids)
    l = n - i
    print(m, n, i, l, n == m * i + 1, l == (m - 1) * i + 1)
# 2 21 10 11 True True
# 3 31 10 21 True True
# 5 51 10 41 True True

def children_of(k, m, size):
    return [c for c in range(m * k + 1, m * k + m + 1) if c < size]

def parent_of(k, m):
    return (k - 1) // m if k > 0 else None

print(children_of(3, 3, 13), parent_of(11, 3))         # [10, 11, 12] 3   a 13-vertex ternary tree

Key takeaways

• In a full m-ary tree, n = m·i + 1 and n = i + l, so any one of n, i, l determines the other two.
• In a full binary tree, l = i + 1: one more leaf than internal vertices.
• Height h allows at most m^h leaves, so l leaves force h ≥ ⌈log_m l⌉.
• A complete tree fits in an array: the children of k are m·k + 1, …, m·k + m.

Practice

1. (Beginner) How many matches are played in a single-elimination tournament with 100 players, where some players get a bye in the first round? Explain the answer with a full binary tree.
2. (Intermediate) Is there a full 3-ary tree with 84 leaves? With 100 vertices? How many internal vertices does a full 5-ary tree with 817 leaves have? Hint: use the table, and check which quantities must be integers.
3. (Interview) A database index is a B-tree in which every node has up to 500 children. Roughly how many levels are needed to index one billion keys, and why do databases choose such a large branching factor? Hint: compute log₅₀₀(10⁹), and remember that each level visited costs one disk or page read.

Tree Height and Balance

Why. Most operations on a rooted tree walk from the root down to some vertex: searching a binary search tree, inserting into a heap, resolving a path in a file system. Their cost is proportional to the height. A tree with n vertices can have height anywhere from about log n (bushy) to n − 1 (a path). Keeping a tree balanced is what turns O(n) operations into O(log n) operations.

What. For a binary tree of height h with n vertices,

  h + 1 ≤ n ≤ 2^{h+1} − 1,      so      ⌈log₂(n + 1)⌉ − 1 ≤ h ≤ n − 1

The upper bound on n was proved by structural induction in 3.3. The lower bound on h is reached by the most compact trees, and the upper bound by a path.

A rooted m-ary tree of height h is balanced if all its leaves are at level h or h − 1. If a full m-ary tree with l leaves is balanced, then its height is exactly h = ⌈log_m l⌉, so it is as short as any tree with that many leaves can be.

Data structures use several related notions of balance:

Notion	Condition	Height guarantee	Used in
Perfect	Full, with all leaves on the same level	h = log₂(n + 1) − 1 exactly	Idealized analysis
Complete	Every level is full except the last, which is filled from the left	h = ⌊log₂ n⌋	Binary heaps
Leaves on two levels	All leaves at level h or h − 1	h = ⌈log_m l⌉ for full trees	Decision-tree bounds
Height-balanced (AVL)	At every vertex, the heights of the two subtrees differ by at most 1	h < 1.45 log₂(n + 2)	AVL trees
Red-black	No red vertex has a red child, and every root-to-leaf path has the same number of black vertices	h ≤ 2 log₂(n + 1)	Java TreeMap, C++ std::map

Why AVL trees have logarithmic height. Let N(h) be the fewest vertices in an AVL tree of height h. The sparsest such tree has a root, one sparsest subtree of height h − 1, and one of height h − 2, so

  N(0) = 1,   N(1) = 2,   N(h) = 1 + N(h − 1) + N(h − 2)

This is a Fibonacci-like recurrence (6.1). In fact N(h) = F_{h+3} − 1, so N(h) grows like φ^h with φ ≈ 1.618. Turning this around, an AVL tree with n vertices has height at most about log_φ n ≈ 1.44 log₂ n.

Analogy. Height is the number of floors in an office building, and an operation is a walk up the stairs. A balanced tree is a wide, low building where you never climb far. A degenerate tree is a one-room-per-floor tower where reaching the top room takes n − 1 flights.

Example.

      balanced (h = 2, n = 6)          degenerate (h = 3, n = 4)

             •                          •
           ╱   ╲                          ╲
          •     •                           •
         ╱ ╲   ╱                              ╲
        •   • •                                 •
                                                  ╲
                                                    •

import math

def height(t):                           # t is None (the empty tree) or a pair (left, right)
    return -1 if t is None else 1 + max(height(t[0]), height(t[1]))

def is_height_balanced(t):
    """Return (balanced?, height) in a single pass, so the check costs O(n), not O(n²)."""
    if t is None:
        return True, -1
    ok_left, h_left = is_height_balanced(t[0])
    ok_right, h_right = is_height_balanced(t[1])
    return ok_left and ok_right and abs(h_left - h_right) <= 1, 1 + max(h_left, h_right)

leaf = (None, None)
bushy = ((leaf, leaf), (leaf, None))
path = (None, (None, (None, leaf)))
print(is_height_balanced(bushy), is_height_balanced(path))   # (True, 2) (False, 3)

N = [1, 2]                               # fewest vertices in an AVL tree of height 0, 1, 2, ...
while len(N) < 15:
    N.append(1 + N[-1] + N[-2])          # root + the sparsest subtrees of heights h − 1 and h − 2
print(N[:11])                            # [1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232]

n = 1000
best = math.ceil(math.log2(n + 1)) - 1                   # most compact binary tree
avl_worst = max(h for h, k in enumerate(N) if k <= n)    # tallest possible AVL tree
print(best, avl_worst, n - 1)            # 9 13 999   the AVL bound is close to the ideal, a path is not

Key takeaways

• Root-to-vertex operations cost O(h), and for binary trees ⌈log₂(n + 1)⌉ − 1 ≤ h ≤ n − 1.
• A balanced full m-ary tree with l leaves has the minimum possible height, ⌈log_m l⌉.
• AVL and red-black trees relax perfect balance just enough to make updates cheap, while still guaranteeing h = O(log n).
• Check height-balance in one pass by returning heights from the recursion. Recomputing heights at every vertex costs O(n²) on a path.

Practice

1. (Beginner) What are the minimum and maximum heights of a binary tree with 15 vertices? Of a full binary tree with 15 vertices?
2. (Intermediate) Prove by induction on h that an m-ary tree of height h has at most m^h leaves. Deduce that a balanced full m-ary tree with l leaves has height exactly ⌈log_m l⌉.
3. (Interview) Write a function that decides whether a binary tree is height-balanced. Your first version probably calls height at every vertex. What is its worst-case running time, and how do you make it linear? Hint: consider a path. Then let the recursion return the height, together with a flag or a sentinel value such as −2 meaning "unbalanced".

Counting Trees and Cayley's Formula

Why. How many different ways are there to connect n labeled computers with n − 1 cables so that all of them can communicate? Equivalently, how many spanning trees does the complete graph Kₙ have? The answer, n^{n−2}, is one of the most elegant formulas in combinatorics, and its standard proof turns each tree into a short sequence of numbers. That encoding also gives a simple way to generate uniformly random trees for testing.

What. Two kinds of counts are common:

• Labeled trees on the vertex set {1, …, n}. Two trees are different if their edge sets differ, even when they have the same shape.
• Unlabeled trees, counted up to isomorphism (8.2), so only the shape matters.

Cayley's formula. There are exactly n^{n−2} labeled trees on n vertices.

n	1	2	3	4	5	6	7	8
Labeled trees n^{n−2}	1	1	3	16	125	1296	16807	262144
Unlabeled trees	1	1	1	2	3	6	11	23

For n = 4 there are two shapes. The path can be labeled in 4!/2 = 12 ways (a path read backwards is the same tree), and the star in 4 ways (choose the center), giving 12 + 4 = 16. Unlabeled trees have no closed formula.

Proof idea: Prüfer sequences. There is a bijection (2.2) between labeled trees on {1, …, n} and sequences of length n − 2 with entries in {1, …, n}. Since there are n^{n−2} such sequences (5.1), there are n^{n−2} trees.

• Encode. Repeat n − 2 times: remove the leaf with the smallest label, and write down its neighbor.
• Decode. Each vertex v appears in the sequence exactly deg(v) − 1 times, so the degrees are known. For each entry s in turn, join s to the smallest-labeled vertex that currently has degree 1 and has not been used yet, then decrease both degrees. At the end, exactly two vertices of degree 1 remain. Join them.

Because v appears deg(v) − 1 times, the leaves are exactly the labels that do not appear. This also counts trees with a prescribed degree sequence: the number of labeled trees in which vertex i has degree dᵢ is the multinomial coefficient (n − 2)! / ∏ (dᵢ − 1)! (5.3).

Example.

   1       2
     ╲   ╱
       4 ───── 5 ───── 6 ───── 7        Prüfer sequence: 4, 4, 4, 5, 6
     ╱
   3

Remove 1 (write 4), remove 2 (write 4), remove 3 (write 4). Now 4 is a leaf, and it is the smallest leaf: remove it (write 5). Then remove 5 (write 6). The vertices 6 and 7 remain.

import heapq
from itertools import combinations, product

def prufer_encode(n, edges):
    adj = {v: set() for v in range(1, n + 1)}
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)
    leaves = [v for v in adj if len(adj[v]) == 1]
    heapq.heapify(leaves)                              # min-heap: the smallest leaf is always on top
    seq = []
    for _ in range(n - 2):
        leaf = heapq.heappop(leaves)
        (nbr,) = adj[leaf]                             # a leaf has exactly one neighbor
        seq.append(nbr)
        adj[nbr].remove(leaf)
        if len(adj[nbr]) == 1:
            heapq.heappush(leaves, nbr)                # removing the leaf may create a new one
    return seq

def prufer_decode(seq):
    n = len(seq) + 2
    degree = {v: 1 for v in range(1, n + 1)}
    for s in seq:
        degree[s] += 1                                 # v appears deg(v) − 1 times
    leaves = [v for v in degree if degree[v] == 1]
    heapq.heapify(leaves)
    edges = []
    for s in seq:
        leaf = heapq.heappop(leaves)
        edges.append((leaf, s))
        degree[s] -= 1
        if degree[s] == 1:
            heapq.heappush(leaves, s)
    edges.append(tuple(sorted(leaves)))                # the last two vertices of degree 1
    return edges

edges = [(1, 4), (2, 4), (3, 4), (4, 5), (5, 6), (6, 7)]
seq = prufer_encode(7, edges)
print(seq)                                             # [4, 4, 4, 5, 6]
print(prufer_decode(seq) == edges)                     # True

def find(root, x):
    while root[x] != x:
        x = root[x]
    return x

def count_labeled_trees(n):
    """Brute force: subsets of n − 1 edges of K_n with no cycle (characterization 4)."""
    count = 0
    for subset in combinations(list(combinations(range(1, n + 1), 2)), n - 1):
        root = list(range(n + 1))
        for u, v in subset:
            ru, rv = find(root, u), find(root, v)
            if ru == rv:                               # u and v already connected: a cycle
                break
            root[ru] = rv
        else:
            count += 1
    return count

print([count_labeled_trees(n) for n in range(2, 7)])  # [1, 3, 16, 125, 1296]
print([n ** (n - 2) for n in range(2, 7)])            # [1, 3, 16, 125, 1296]

n = 6
trees = {frozenset(map(frozenset, prufer_decode(list(s)))) for s in product(range(1, n + 1), repeat=n - 2)}
print(len(trees))                                      # 1296: different sequences give different trees

Key takeaways

• There are n^{n−2} labeled trees on n vertices (Cayley), so Kₙ has n^{n−2} spanning trees.
• Prüfer sequences are a bijection between labeled trees and sequences of length n − 2 over {1, …, n}.
• Vertex v appears deg(v) − 1 times in the Prüfer sequence, and the leaves are the labels that never appear.
• Unlabeled trees (shapes up to isomorphism) are far fewer and have no closed formula.

Practice

1. (Beginner) Draw the 3 labeled trees on {1, 2, 3} and the 16 on {1, 2, 3, 4}, grouped by shape. What is the Prüfer sequence of the star whose center is k?
2. (Intermediate) Use Prüfer sequences to count the labeled trees on {1, …, n} in which vertex 1 is a leaf. Deduce the probability that a fixed vertex is a leaf in a uniformly random labeled tree, and its limit as n → ∞. Hint: vertex 1 is a leaf exactly when it does not appear in the sequence.
3. (Interview) You need uniformly random labeled trees on n vertices to fuzz-test a network-topology tool. How do you generate one in O(n log n)? Why is "attach each new vertex k to a uniformly random earlier vertex" not uniform? Hint: use a random Prüfer sequence. For the second question, try n = 3: which of the 3 trees can never be produced?

<a id="92-applications-of-trees"></a>

9.2 Applications of Trees

Trees show up wherever a process branches: a comparison goes left or right, a question has several answers, a bit is 0 or 1, players take turns choosing moves. This subchapter studies four such uses: search trees for ordered data, decision trees for lower bounds, Huffman trees for compression, and game trees for adversarial search.

Binary Search Trees

Why. A sorted array supports binary search in O(log n), but inserting a new key means shifting up to n elements. A linked list supports O(1) insertion, but searching it takes O(n). A binary search tree combines the strengths of both: search, insertion and deletion all follow a single root-to-leaf path. Unlike a hash table, it also keeps the keys in order, so it can answer "smallest key", "next key after x" and "all keys between a and b".

What. A binary search tree (BST) is a binary tree in which each vertex stores a key, and for every vertex v

  every key in the left subtree of v  <  key(v)  <  every key in the right subtree of v

As a consequence, the inorder traversal (9.3) lists the keys in increasing order.

How.

• Search for x: start at the root. If x equals the key, stop. If x is smaller, go left. Otherwise go right. Falling off the tree means x is absent.
• Insert x: search for x, and attach a new leaf at the place where the search fell off.
• Delete x: if its vertex has no children, remove it. If it has one child, splice the child into its place. If it has two children, copy in its inorder successor (the smallest key in its right subtree, which has no left child), then delete the successor from the right subtree.

Each operation costs O(h), where h is the height of the tree.

The shape depends on the insertion order. Inserting keys in sorted order produces a path with h = n − 1, and every operation degrades to O(n). Inserting a random permutation gives an expected height of O(log n) (about 4.3 ln n), and an average vertex depth of about 2 ln n ≈ 1.39 log₂ n. Self-balancing BSTs, such as AVL and red-black trees (9.1), restore balance with local restructurings called rotations, which guarantees h = O(log n) for every insertion order.

Structure	Search	Insert	Delete	Ordered queries (min, successor, range)
Sorted array	O(log n)	O(n)	O(n)	Yes
Unsorted linked list	O(n)	O(1)	O(n) (find, then O(1) unlink)	No
Hash table	O(1) average	O(1) average	O(1) average	No
BST, unbalanced	O(h), worst case O(n)	O(h)	O(h)	Yes
BST, self-balancing	O(log n)	O(log n)	O(log n)	Yes

Example. Inserting 50, 30, 70, 20, 40, 60, 80, 35 in that order:

               50
            ╱      ╲
          30        70              search 35:  50 → 30 → 40 → 35   found
         ╱  ╲      ╱  ╲             search 65:  50 → 70 → 60 → (no right child)   absent
       20    40  60    80
            ╱
          35

import random

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

def insert(root, key):
    new = Node(key)
    if root is None:
        return new
    cur = root
    while True:                                       # iterative, so a tall tree cannot overflow the stack
        if key == cur.key:
            return root                               # duplicate keys are ignored
        side = "left" if key < cur.key else "right"
        nxt = getattr(cur, side)
        if nxt is None:
            setattr(cur, side, new)                   # the search fell off here: attach the new leaf
            return root
        cur = nxt

def search_path(root, key):
    path = []
    while root is not None:
        path.append(root.key)
        if key == root.key:
            return path, True
        root = root.left if key < root.key else root.right
    return path, False

def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    elif root.left is None or root.right is None:     # zero or one child: splice the vertex out
        return root.left or root.right
    else:                                             # two children: copy in the inorder successor
        succ = root.right
        while succ.left is not None:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root

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

def height(t):
    return -1 if t is None else 1 + max(height(t.left), height(t.right))

root = None
for k in [50, 30, 70, 20, 40, 60, 80, 35]:
    root = insert(root, k)
print(inorder(root))                 # [20, 30, 35, 40, 50, 60, 70, 80]
print(search_path(root, 35))         # ([50, 30, 40, 35], True)
print(search_path(root, 65))         # ([50, 70, 60], False)
root = delete(root, 30)              # 30 has two children: its successor 35 takes its place
print(root.left.key, inorder(root))  # 35 [20, 35, 40, 50, 60, 70, 80]

keys = list(range(500))
sorted_tree = None
for k in keys:
    sorted_tree = insert(sorted_tree, k)
random.seed(7)
random.shuffle(keys)
random_tree = None
for k in keys:
    random_tree = insert(random_tree, k)
print(height(sorted_tree), height(random_tree))   # 499 21   a path versus a bushy tree

Key takeaways

• BST property: left subtree < vertex < right subtree. The inorder traversal is sorted.
• Search, insertion and deletion follow one root-to-leaf path, so each costs O(h).
• Deleting a vertex with two children replaces it with its inorder successor.
• Sorted insertions degrade a plain BST into a path. Self-balancing trees guarantee O(log n) height.
• Choose a BST over a hash table when you need ordered queries.

Practice

1. (Beginner) Insert 8, 3, 10, 1, 6, 14, 4, 7, 13 into an empty BST. Draw the result, give the search paths for 7 and 5, then delete 3 and redraw the tree.
2. (Intermediate) Show that the number of different BST shapes on the keys {1, …, n} is the Catalan number Cₙ (5.6). Hint: if the root is i, the left subtree is a BST on i − 1 keys and the right subtree is a BST on n − i keys.
3. (Interview) Validate a BST. Given a binary tree, decide whether it satisfies the BST property. Hint: comparing each vertex only with its two children is wrong (find a counterexample of height 2). Instead, pass down an allowed interval (low, high), or check that the inorder sequence is strictly increasing.

Decision Trees

Why. Many algorithms learn about their input only by asking questions: "is a[i] < a[j]?", "which pan of the balance is heavier?", "is the test positive?". Every such algorithm can be drawn as a tree of questions and answers, and its worst-case number of questions is the height of that tree. Since a tree of small height cannot have many leaves (9.1), this gives lower bounds: statements that no algorithm of this kind can do better. The best-known one is that comparison sorting needs Ω(n log n) comparisons.

What. A decision tree is a rooted tree in which

• every internal vertex is a question,
• every edge leaving it is one possible answer, and
• every leaf is a final outcome.

Running the algorithm on an input follows one root-to-leaf path. If the problem has L possible outcomes, each needs its own leaf. If every question has at most m answers, the tree is m-ary, so

  worst-case number of questions  =  height  ≥  ⌈log_m L⌉

Example 1: the counterfeit coin. Among 8 identical-looking coins, one is lighter than the others. A balance scale has 3 outcomes (left lighter, balanced, right lighter), and there are 8 possible answers, so at least ⌈log₃ 8⌉ = 2 weighings are needed. Two weighings suffice:

                         weigh {1, 2, 3} against {4, 5, 6}
                ╱                       │                       ╲
         left lighter                balanced                right lighter
               │                        │                         │
          weigh 1 vs 2             weigh 7 vs 8              weigh 4 vs 5
         ╱     │     ╲             ╱         ╲               ╱     │     ╲
        1      3      2           7           8             4      6      5

Example 2: sorting. A comparison sort on n distinct keys must distinguish all n! orderings, and each comparison has 2 outcomes. So every comparison sort needs at least ⌈log₂ n!⌉ comparisons in the worst case. Since n! ≥ (n/2)^{n/2},

  log₂ n!  ≥  (n/2) log₂(n/2)  =  Ω(n log n)

Merge sort and heapsort use O(n log n) comparisons, so they are optimal up to a constant factor. A decision tree for sorting a, b, c has 3! = 6 leaves and height 3:

                           a < b ?
                  yes ╱              ╲ no
                b < c ?                a < c ?
               ╱      ╲               ╱      ╲
          a<b<c      a < c ?      b<a<c      b < c ?
                    ╱      ╲                ╱      ╲
                a<c<b    c<a<b          b<c<a    c<b<a

The bound is not always reached. For n = 12, ⌈log₂ 12!⌉ = 29, but it has been proved that 30 comparisons are needed.

n	3	4	5	6	7	8	10	100
⌈log₂ n!⌉	3	5	7	10	13	16	22	525

import math
from itertools import permutations

def merge_sort(a, counter):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid], counter), merge_sort(a[mid:], counter)
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        counter[0] += 1                               # one comparison = one internal vertex on the path
        if left[i] < right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    return out + left[i:] + right[j:]

print(" n  bound  merge sort (worst case over all n! inputs)")
for n in range(1, 9):
    worst = 0
    for p in permutations(range(n)):
        counter = [0]
        merge_sort(list(p), counter)
        worst = max(worst, counter[0])
    print(f"{n:2} {math.ceil(math.log2(math.factorial(n))):6} {worst:6}")
#  n  bound  merge sort (worst case over all n! inputs)
#  1      0      0
#  2      1      1
#  3      3      3
#  4      5      5
#  5      7      8
#  6     10     11
#  7     13     14
#  8     16     17

Merge sort meets the bound up to n = 4 and needs one comparison more for n = 5, …, 8. That is still O(n log n), so the gap is only a lower-order term.

Decision trees in machine learning. A decision-tree classifier is the same structure learned from data. Each internal vertex tests a feature ("income > 40k?"), each leaf predicts a class, and training chooses at every vertex the question that best separates the examples, for example the one with the largest reduction in entropy.

Key takeaways

• An algorithm that only asks questions is a decision tree. Its worst-case cost is the tree's height.
• L outcomes and at most m answers per question force at least ⌈log_m L⌉ questions.
• Comparison sorting needs ⌈log₂ n!⌉ = Ω(n log n) comparisons, so merge sort is asymptotically optimal.
• The bound counts outcomes only. Sometimes a smarter argument gives a stronger bound.

Practice

1. (Beginner) With 12 coins, one of them lighter, what does the decision-tree bound give for a balance scale? Design a strategy that meets the bound. Repeat for 9 coins.
2. (Intermediate) Show that finding the maximum of n distinct numbers needs n − 1 comparisons, and explain why the decision-tree bound ⌈log₂ n⌉ is far too weak here. Hint: every element other than the maximum must lose at least one comparison, and each comparison has only one loser.
3. (Interview) You have 1000 bottles of wine, exactly one of them poisoned. A test strip shows the result after 24 hours, and you have only one day. What is the smallest number of strips that identifies the poisoned bottle, and how do you use them? Hint: each strip gives a yes/no answer and all strips are read together, so k strips have 2^k outcomes. Think of the bottle number in binary.

Huffman Coding

Why. ASCII spends 8 bits on every character, whether it is the very common e or the rare z. Giving short codes to frequent symbols and long codes to rare ones saves space, but the encoded bits must still decode without ambiguity, and there are no separators between codewords. Prefix codes solve the decoding problem, prefix codes are exactly binary trees, and Huffman's greedy algorithm finds the best tree. Huffman coding is a building block of DEFLATE (zip, gzip, PNG), JPEG and MP3.

What. A prefix code assigns each symbol a bit string such that no codeword is a prefix of another. With such a code, the decoder reads bits until they form a complete codeword, outputs that symbol, and starts again. No lookahead is needed.

Prefix codes correspond to binary trees whose leaves are the symbols. Label each left edge 0 and each right edge 1. The codeword of a symbol is the label sequence on the path from the root to its leaf. A codeword cannot be a prefix of another, because leaves have no descendants. If symbol s has frequency f(s), the cost of the code is

  B(T) = Σ_s f(s) · depth_T(s)        (total number of encoded bits)

Huffman's algorithm.

1. Make a single-vertex tree for each symbol, with weight f(s).
2. Repeatedly remove the two trees with the smallest weights, and join them as the two children of a new root whose weight is the sum of theirs.
3. Stop when one tree remains.

With a min-heap as the priority queue, this takes O(k log k) for k symbols.

Why it is optimal (sketch). An exchange argument shows that some optimal tree has the two least frequent symbols x and y as sibling leaves at the deepest level. Merging them into one symbol of weight f(x) + f(y) gives a smaller problem, and every tree for the merged problem costs exactly f(x) + f(y) less than the corresponding tree for the original one. By induction, solving the smaller problem optimally solves the original one. Huffman's average codeword length is also within 1 bit of the entropy, H = −Σ p(s) log₂ p(s), which is the theoretical minimum.

Example. A file of 100,000 characters over a, …, f, with these frequencies in thousands:

Symbol	a	b	c	d	e	f
Frequency	45	13	12	16	9	5
Fixed-length code	000	001	010	011	100	101
Huffman code	0	101	100	111	1101	1100

The merges are f + e = 14, c + b = 25, 14 + d = 30, 25 + 30 = 55 and a + 55 = 100:

                 (100)
               0╱     ╲1
             a:45     (55)
                    0╱    ╲1
                 (25)      (30)
                0╱  ╲1    0╱  ╲1
             c:12  b:13 (14)  d:16
                       0╱  ╲1
                      f:5  e:9

The cost is 45·1 + (13 + 12 + 16)·3 + (9 + 5)·4 = 224 thousand bits, against 300 thousand with the 3-bit fixed code, a 25% saving.

import heapq
from itertools import count

def huffman(freq):
    tick = count()                                       # tie-breaker, so the heap never compares trees
    heap = [(f, next(tick), sym) for sym, f in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        f1, _, left = heapq.heappop(heap)                # the two lightest trees
        f2, _, right = heapq.heappop(heap)
        heapq.heappush(heap, (f1 + f2, next(tick), (left, right)))
    codes = {}
    def walk(t, prefix):
        if isinstance(t, tuple):                         # internal vertex: (left, right)
            walk(t[0], prefix + "0")
            walk(t[1], prefix + "1")
        else:
            codes[t] = prefix or "0"                     # a one-symbol alphabet still needs one bit
    walk(heap[0][2], "")
    return codes

def decode(bits, codes):
    symbol_of, out, cur = {c: s for s, c in codes.items()}, [], ""
    for b in bits:
        cur += b
        if cur in symbol_of:                             # prefix property: the first match is the symbol
            out.append(symbol_of[cur])
            cur = ""
    return "".join(out)

freq = {"a": 45, "b": 13, "c": 12, "d": 16, "e": 9, "f": 5}
codes = huffman(freq)
print(dict(sorted(codes.items())))
# {'a': '0', 'b': '101', 'c': '100', 'd': '111', 'e': '1101', 'f': '1100'}
print(sum(freq[s] * len(codes[s]) for s in freq))        # 224   versus 300 with a 3-bit fixed code

bits = "".join(codes[ch] for ch in "facade")
print(bits, decode(bits, codes))                         # 1100010001111101 facade

Key takeaways

• A prefix code is a binary tree: symbols are leaves, and a codeword is the 0/1 path from the root.
• Prefix codes decode greedily, with no separators and no lookahead.
• Huffman's algorithm repeatedly merges the two lightest trees. It is greedy and provably optimal among prefix codes.
• An optimal code tree is always a full binary tree, and its average length is within 1 bit of the entropy.
• The decoder needs the code as well as the bits. Real formats send only the codeword lengths (canonical Huffman codes).

Practice

1. (Beginner) Build a Huffman code for the letters of mississippi (i: 4, s: 4, p: 2, m: 1). How many bits does the encoded word take, compared with a 2-bit fixed-length code? Do ties change the total?
2. (Intermediate) Prove that the tree of an optimal prefix code is full: no internal vertex has only one child. Then show that if every frequency is a power of 1/2, the Huffman code's average length equals the entropy exactly.
3. (Interview) You are compressing large log files whose words come from a vocabulary of about 50 tokens with very skewed frequencies. What must the compressed file contain besides the encoded bits, and how would you make that part small? When would Huffman coding over single tokens be a poor choice? Hint: look up canonical Huffman codes. Then think about repeated multi-token phrases, which LZ-style compression captures and per-symbol codes cannot.

Game Trees and Minimax

Why. In two-player games with perfect information, such as tic-tac-toe, checkers, chess or Nim, you want the move that is best assuming your opponent also plays as well as possible. A game tree lays out every possible continuation. Minimax assigns a value to each position by working upward from the end of the game. Alpha-beta pruning gets the same answer while skipping branches that cannot affect it. The same adversarial reasoning applies to security games, negotiation, and worst-case analysis of algorithms.

What. In a game tree,

• each vertex is a position, and the root is the current position,
• the children of a vertex are the positions reachable in one legal move,
• levels alternate between the two players, called MAX and MIN, and
• each leaf is a finished game labeled with its payoff to MAX (for example +1 win, 0 draw, −1 loss).

The minimax value of a vertex is defined recursively:

  value(v) = payoff(v)                        if v is a leaf
           = max over children c of value(c)  if MAX is to move at v
           = min over children c of value(c)  if MIN is to move at v

The value of the root is the outcome when both players play perfectly. Computing it is a postorder traversal (9.3): children are evaluated before their parent.

How big are game trees? Tic-tac-toe has 255,168 possible games, which is easy to search completely. Chess has roughly 10^{120} (Shannon's estimate), which is impossible. Real programs therefore cut the search off at a fixed depth, estimate the value of positions there with a heuristic evaluation function, and prune.

Alpha-beta pruning. While searching, keep two bounds:

• α: the best value MAX can already guarantee on the path to the root, and
• β: the best value MIN can already guarantee.

As soon as α ≥ β at some vertex, the player to move earlier on the path will never allow the game to reach it, so its remaining children are skipped. The root value is exactly the minimax value. With good move ordering, alpha-beta examines about b^{d/2} leaves instead of b^d, so it can search twice as deep in the same time.

Example.

 MAX                         A = 3
                   ╱           │           ╲
 MIN            B = 3        C ≤ 2        D = 2
              ╱   │   ╲     ╱  ┊  ┊     ╱   │   ╲
             3   12    8   2   4  6   14    5    2
                               (pruned)

B = min(3, 12, 8) = 3, so MAX can already guarantee 3 (α = 3). At C, the first leaf is 2, so C ≤ 2 < 3. MAX will never choose C, and the leaves 4 and 6 are never examined. D = 2, so A = max(3, ≤ 2, 2) = 3.

import math
from functools import lru_cache

def minimax(node, maximizing):
    if isinstance(node, int):                            # leaf: payoff to MAX
        return node
    values = [minimax(child, not maximizing) for child in node]
    return max(values) if maximizing else min(values)

def alphabeta(node, maximizing, seen, alpha=-math.inf, beta=math.inf):
    if isinstance(node, int):
        seen.append(node)                                # record which leaves were actually evaluated
        return node
    best = -math.inf if maximizing else math.inf
    for child in node:
        v = alphabeta(child, not maximizing, seen, alpha, beta)
        if maximizing:
            best = max(best, v)
            alpha = max(alpha, best)
        else:
            best = min(best, v)
            beta = min(beta, best)
        if alpha >= beta:                                # the opponent will never allow this line
            break
    return best

tree = [[3, 12, 8], [2, 4, 6], [14, 5, 2]]
seen = []
print(minimax(tree, True), alphabeta(tree, True, seen), seen)
# 3 3 [3, 12, 8, 2, 14, 5, 2]

@lru_cache(maxsize=None)
def wins(stones):
    """Take 1, 2 or 3 stones per turn; whoever takes the last stone wins.
    The player to move wins if some move leaves the opponent in a losing position."""
    return any(not wins(stones - k) for k in (1, 2, 3) if k <= stones)

print([n for n in range(1, 21) if not wins(n)])          # [4, 8, 12, 16, 20]   losing positions

The memoization in wins matters: the game tree for 20 stones has 266,079 vertices, but it contains only 21 different positions. Treating repeated positions as one vertex turns the tree into a DAG. Chess programs do the same with a transposition table.

Key takeaways

• A game tree alternates MAX and MIN levels. Leaves carry payoffs to MAX.
• Minimax takes the max at MAX vertices and the min at MIN vertices. The root value is the result of perfect play.
• Minimax is a postorder computation: children are evaluated before their parent.
• Alpha-beta pruning returns the same value while skipping branches that cannot matter. With good move ordering, it roughly doubles the search depth.
• Large games need a depth limit with a heuristic evaluation, plus memoization of repeated positions.

Practice

1. (Beginner) Compute the minimax value of the tree [[5, 6], [7, 4, 5], [3]], with MAX at the root. Which leaves does alpha-beta skip when it searches left to right?
2. (Intermediate) Prove by strong induction that in the take-1-2-or-3 game, the player to move loses exactly when the number of stones is a multiple of 4. Generalize to "take between 1 and k stones".
3. (Interview) Write a tic-tac-toe AI that never loses, then explain how you would scale the approach to Connect Four. Hint: full minimax is fine for tic-tac-toe, and symmetry plus memoization makes it faster. For Connect Four, add alpha-beta, a depth limit with an evaluation function (for example, counting open lines), move ordering (center columns first) and a transposition table.

<a id="93-tree-traversal"></a>

9.3 Tree Traversal

A traversal visits every vertex of an ordered rooted tree exactly once, in a systematic order. The three depth-first orders differ only in when a vertex is visited relative to its subtrees, and each order suits a different kind of computation. The subchapter ends by using all three on arithmetic expressions. All the examples use this binary tree:

                 A
              ╱     ╲
             B       C              preorder:     A B D E G H C F
           ╱   ╲       ╲            inorder:      D B G E H A C F
          D     E       F           postorder:    D G H E B F C A
               ╱ ╲                  level order:  A B C D E F G H
              G   H

A useful picture for all three orders is to walk around the outside of the tree, going down its left side first and keeping the tree on your left. This walk is called an Euler tour. You pass each vertex on its left, then underneath it (between its subtrees), then on its right. Preorder lists vertices the first time you pass them, inorder lists them when you pass underneath, and postorder lists them the last time you pass them.

Preorder Traversal

Why. Often a vertex must be handled before its descendants, because the children need something from the parent: printing a directory listing with indentation, copying a tree (create the parent, then attach copies of its children), serializing a tree to a file, generating a table of contents. Preorder does exactly that.

What. The preorder traversal of an ordered rooted tree T with root r and subtrees T₁, …, T_k (left to right) is:

  preorder(T) = r, preorder(T₁), preorder(T₂), …, preorder(T_k)

Visit the root, then traverse each subtree in preorder, from left to right. On a rooted tree, preorder is exactly the order in which DFS (8.4) discovers the vertices.

Universal address system. Label the root 0, its children 1, 2, …, k from left to right, and the children of a vertex with label A as A.1, A.2, …. Sorting these labels lexicographically gives exactly the preorder. For the example tree:

Vertex	A	B	D	E	G	H	C	F
Address	0	1	1.1	1.2	1.2.1	1.2.2	2	2.1

The section numbers of this document, such as 9.3, form the same kind of system. Reading the document from start to finish is a preorder traversal of its outline.

How. Recursively, visit the vertex and then recurse on its children in order. Iteratively, use a stack. Pop a vertex, visit it, and push its children from right to left, so that the leftmost child is popped first. Both versions take O(n) time. The recursion uses O(h) stack space.

tree = {"A": ("B", "C"), "B": ("D", "E"), "C": (None, "F"), "E": ("G", "H")}   # vertex: (left, right)

def kids(t, v):
    return [c for c in t.get(v, (None, None)) if c is not None]

def preorder(t, v):
    yield v                                              # visit the root first ...
    for c in kids(t, v):
        yield from preorder(t, c)                        # ... then each subtree, left to right

def preorder_iterative(t, root):
    stack, out = [root], []
    while stack:
        v = stack.pop()
        out.append(v)
        stack.extend(reversed(kids(t, v)))               # push right to left, so the left child pops first
    return out

print("".join(preorder(tree, "A")), "".join(preorder_iterative(tree, "A")))   # ABDEGHCF ABDEGHCF

fs = {"/": ["etc", "home"], "etc": ["hosts"], "home": ["ana", "ben"], "ana": ["notes.md"]}

def listing(v, depth=0):
    print("  " * depth + v)                              # a directory is printed before its contents
    for c in fs.get(v, []):
        listing(c, depth + 1)

listing("/")
# /
#   etc
#     hosts
#   home
#     ana
#       notes.md
#     ben

Key takeaways

• Preorder visits the root, then the subtrees from left to right.
• Use it when the parent must be handled before its children: copying, serializing, printing hierarchies.
• Preorder is the DFS discovery order, and it is the lexicographic order of universal addresses.
• The iterative version pushes children onto a stack from right to left.

Practice

1. (Beginner) Give the preorder of the file-system tree from 9.1 (/, etc, home, usr, …). Assign universal addresses to its vertices and check that sorting the addresses reproduces the preorder.
2. (Intermediate) Find two different binary trees with the same preorder sequence. Then explain why the preorder together with the inorder sequence determines a binary tree with distinct labels. Hint: the first preorder element is the root, and its position in the inorder sequence splits the remaining elements into the left and right subtrees.
3. (Interview) Serialize and deserialize a binary tree. Design serialize(root) -> str and deserialize(str) -> root. Hint: a preorder listing with an explicit marker for every missing child (for example #) determines the tree uniquely. Deserialization reads one token: if it is #, return nothing. Otherwise create the vertex, and then build its left and right subtrees recursively from the remaining tokens.

Inorder Traversal

Why. For a binary search tree, visiting the left subtree, then the root, then the right subtree lists the keys in sorted order. Inorder is also the order in which we write ordinary infix expressions like a + b: left operand, operator, right operand. Any time the left-to-right position of the vertices in a drawing matters, inorder is the right traversal.

What. For a binary tree:

  inorder(T) = inorder(left subtree), root, inorder(right subtree)

An empty subtree contributes nothing. In a binary tree, a single child counts as either a left or a right child, and the difference matters: in the example tree, C comes before its right child F. For a general ordered rooted tree, inorder is defined as: the first subtree, then the root, then the remaining subtrees from left to right. That definition is rarely used in practice.

Analogy. Press the drawing of the tree flat onto a horizontal line, letting every vertex fall straight down. If each left subtree is drawn entirely to the left of its root and each right subtree entirely to the right, the vertices land in inorder.

How. Recursively, follow the definition. Iteratively, slide down to the leftmost vertex while pushing every vertex you pass onto a stack. Then pop a vertex, visit it, and repeat from its right child. Both take O(n) time and O(h) space. Morris traversal reaches O(1) extra space by temporarily rewiring null right pointers, and then restoring them.

from itertools import islice

tree = {"A": ("B", "C"), "B": ("D", "E"), "C": (None, "F"), "E": ("G", "H")}   # vertex: (left, right)

def inorder(t, v):
    if v is None:
        return
    left, right = t.get(v, (None, None))
    yield from inorder(t, left)
    yield v                                              # visit between the two subtrees
    yield from inorder(t, right)

def inorder_iterative(t, root):
    stack, out, v = [], [], root
    while stack or v is not None:
        while v is not None:                             # slide down to the leftmost unvisited vertex
            stack.append(v)
            v = t.get(v, (None, None))[0]
        v = stack.pop()
        out.append(v)
        v = t.get(v, (None, None))[1]                    # then traverse its right subtree
    return out

print("".join(inorder(tree, "A")), "".join(inorder_iterative(tree, "A")))   # DBGEHACF DBGEHACF

bst = {50: (30, 70), 30: (20, 40), 70: (60, 80), 40: (35, None)}           # the BST from 9.2
print(list(inorder(bst, 50)))                            # [20, 30, 35, 40, 50, 60, 70, 80]
print(next(islice(inorder(bst, 50), 2, None)))           # 35   third smallest key, found lazily

Because inorder is a generator, asking for the k-th smallest key stops as soon as it is found. Only the vertices on the way there are visited, so this costs O(h + k), not O(n).

Key takeaways

• Inorder visits the left subtree, then the root, then the right subtree.
• On a BST, inorder yields the keys in increasing order, so "is this a BST?" becomes "is the inorder sequence strictly increasing?".
• Whether a single child is on the left or on the right changes the inorder sequence.
• The iterative version slides left while pushing vertices, and then pops and moves right.

Practice

1. (Beginner) Give the inorder sequence of the BST you built in the first exercise of 9.2, and check that it is sorted.
2. (Intermediate) Reconstruct the binary tree with preorder 1 2 4 5 3 6 and inorder 4 2 5 1 6 3. Then prove by strong induction on the number of vertices that the inorder traversal of every BST is sorted.
3. (Interview) Inorder successor. Each BST vertex stores a parent pointer. Given a vertex, return the vertex with the next larger key in O(h) time and O(1) extra space. Hint: there are two cases. If the vertex has a right subtree, the successor is the leftmost vertex of that subtree. Otherwise, climb up until you arrive at a vertex from its left child.

Postorder Traversal

Why. Many computations on a tree need the results for the children before they can handle the parent: the size or height of every subtree, the disk usage of every directory, freeing a tree from memory (children first, or their pointers are lost), evaluating an expression, computing minimax values (9.2), and most dynamic programming on trees. Postorder delivers exactly that order.

What.

  postorder(T) = postorder(T₁), postorder(T₂), …, postorder(T_k), r

Traverse each subtree from left to right, and visit the root last. Postorder is the order in which DFS (8.4) finishes the vertices, and the reverse of a DFS postorder on a DAG is a topological order (8.4).

Traversal	Order	Example tree	Typical uses
Preorder	Root, then subtrees	A B D E G H C F	Copying, serializing, printing hierarchies, prefix notation
Inorder (binary)	Left, root, right	D B G E H A C F	Sorted output of a BST, infix notation
Postorder	Subtrees, then root	D G H E B F C A	Subtree sizes, deletion, evaluation, disk usage, postfix notation
Level order	By level, using BFS (8.4)	A B C D E F G H	Printing level by level, nearest leaf, heap layout

All four take O(n) time. The three depth-first orders use O(h) extra space, and level order uses space proportional to the widest level.

How. Recursively, recurse on all children, then visit. A neat iterative trick: a modified preorder that pushes the left child first visits root, right, left. Reversing that output gives left, right, root, which is postorder.

tree = {"A": ("B", "C"), "B": ("D", "E"), "C": (None, "F"), "E": ("G", "H")}   # vertex: (left, right)

def kids(t, v):
    return [c for c in t.get(v, (None, None)) if c is not None]

def postorder(t, v):
    for c in kids(t, v):
        yield from postorder(t, c)
    yield v                                              # visit after all subtrees

def postorder_iterative(t, root):
    stack, out = [root], []
    while stack:
        v = stack.pop()
        out.append(v)                                    # produces root, right, left ...
        stack.extend(kids(t, v))
    return out[::-1]                                     # ... whose reverse is left, right, root

print("".join(postorder(tree, "A")), "".join(postorder_iterative(tree, "A")))   # DGHEBFCA DGHEBFCA

sizes = {"hosts": 1, "notes.md": 12, "photo.jpg": 2048, "todo.txt": 3}           # file sizes in KB
dirs = {"/": ["etc", "home"], "etc": ["hosts"], "home": ["ana", "ben"],
        "ana": ["notes.md", "photo.jpg"], "ben": ["todo.txt"]}

def du(v, report):
    total = sizes.get(v, 0) + sum(du(c, report) for c in dirs.get(v, []))   # children are summed first
    if v in dirs:
        report.append((v, total))                        # a directory is reported after its contents
    return total

report = []
du("/", report)
print(report)   # [('etc', 1), ('ana', 2060), ('ben', 3), ('home', 2063), ('/', 2064)]

Key takeaways

• Postorder visits the subtrees from left to right, then the root.
• Use it whenever a parent's result depends on its children's results: sizes, heights, deletion, evaluation, minimax.
• Postorder is the DFS finishing order. Reversing it on a DAG gives a topological order.
• Iteratively, run a root-right-left preorder and reverse its output.

Practice

1. (Beginner) Give the postorder of the file-system tree from 9.1. Then check, on the example tree, that the postorder equals the reverse of the preorder of the mirror-image tree.
2. (Intermediate) Show that postorder together with inorder determines a binary tree with distinct labels. Then find two different binary trees with the same preorder and the same postorder. Why can't this happen when both trees are full? Hint: look at a vertex with exactly one child.
3. (Interview) Diameter of a binary tree. Find the number of edges on the longest path between any two vertices, in O(n) time. Hint: in a postorder pass, return each vertex's height. At each vertex, the longest path through it has length height(left) + height(right) + 2, using −1 for an empty subtree. Keep the maximum seen so far.

Expression Trees and Prefix/Postfix Notation

Why. Infix notation like 7 − 3 * 2 is ambiguous without precedence rules and parentheses. An expression tree makes the structure explicit, and walking the tree in preorder or postorder gives prefix and postfix notations, which need no parentheses at all and can be evaluated with a single stack. Compilers turn source code into abstract syntax trees, and stack machines such as the JVM, Python's bytecode interpreter, PostScript and RPN calculators execute postfix code.

What. In an expression tree, every internal vertex is an operator and every leaf is an operand (a number or a variable). A binary operator has a left child (its first operand) and a right child (its second operand). The three traversals give three notations:

Traversal	Notation	For the tree below
Preorder	Prefix, or Polish notation (Łukasiewicz)	+ * − 7 3 2 / 9 3
Inorder, with parentheses around every subexpression	Infix	(((7 − 3) * 2) + (9 / 3))
Postorder	Postfix, or reverse Polish notation (RPN)	7 3 − 2 * 9 3 / +

                +
             ╱     ╲
            *       /
          ╱   ╲    ╱ ╲
         −     2  9   3            value: (7 − 3) * 2 + 9 / 3 = 8 + 3 = 11
        ╱ ╲
       7   3

Prefix and postfix are unambiguous as long as every operator has a fixed number of operands. Unary minus must therefore use a different symbol from binary minus, for example ~.

How: evaluating postfix with a stack. Scan from left to right. Push each operand. For an operator, pop the right operand, then the left operand, apply the operator, and push the result. At the end, the stack holds exactly the value.

Token	7	3	−	2	*	9	3	/	+
Stack after	7	7 3	4	4 2	8	8 9	8 9 3	8 3	11

Prefix is evaluated the same way while scanning from right to left. The popping order is reversed: the first value popped is now the left operand. Building the tree from postfix uses the same stack algorithm, with subtrees pushed instead of numbers.

Converting infix to postfix is done with Dijkstra's shunting-yard algorithm, which keeps operators on a stack and pops them according to precedence. A compiler front end usually builds the tree directly with a recursive-descent parser (Chapter 13).

import operator

OPS = {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv}

def tree_from_postfix(tokens):
    stack = []
    for tok in tokens:
        if tok in OPS:
            right = stack.pop()                          # the right operand was pushed last
            left = stack.pop()
            stack.append((tok, left, right))
        else:
            stack.append(tok)                            # an operand is a leaf
    (root,) = stack                                      # a well-formed expression leaves exactly one tree
    return root

def prefix(t):
    return [t] if isinstance(t, str) else [t[0]] + prefix(t[1]) + prefix(t[2])

def postfix(t):
    return [t] if isinstance(t, str) else postfix(t[1]) + postfix(t[2]) + [t[0]]

def infix(t):
    return t if isinstance(t, str) else f"({infix(t[1])} {t[0]} {infix(t[2])})"

def eval_postfix(tokens):
    stack = []
    for tok in tokens:
        if tok in OPS:
            b, a = stack.pop(), stack.pop()              # right operand on top, left operand below it
            stack.append(OPS[tok](a, b))
        else:
            stack.append(float(tok))
    return stack.pop()

def eval_prefix(tokens):
    stack = []
    for tok in reversed(tokens):                         # scan right to left
        if tok in OPS:
            a, b = stack.pop(), stack.pop()              # now the left operand is on top
            stack.append(OPS[tok](a, b))
        else:
            stack.append(float(tok))
    return stack.pop()

post = "7 3 - 2 * 9 3 / +".split()
t = tree_from_postfix(post)
print(infix(t))                                          # (((7 - 3) * 2) + (9 / 3))
print(" ".join(prefix(t)))                               # + * - 7 3 2 / 9 3
print(postfix(t) == post)                                # True
print(eval_postfix(post), eval_prefix(prefix(t)))        # 11.0 11.0

Key takeaways

• In an expression tree, operators are internal vertices and operands are leaves.
• Preorder gives prefix (Polish) notation, inorder with parentheses gives infix, and postorder gives postfix (RPN).
• Prefix and postfix need no parentheses or precedence rules, as long as every operator has a fixed number of operands.
• Postfix is evaluated left to right with one stack. Prefix is evaluated right to left the same way.
• Infix needs a parser: shunting-yard or recursive descent.

Practice

1. (Beginner) Draw the expression tree of (a + b) * (c − d / e) and write it in prefix and postfix notation. Evaluate the postfix expression 5 1 2 + 4 * + 3 − with a stack.
2. (Intermediate) Prove that a sequence of operands and binary operators is a valid postfix expression if and only if the running count "operands seen minus operators seen" is at least 1 after every token and equals exactly 1 at the end. Hint: the count is the stack height in the evaluation algorithm.
3. (Interview) Implement a calculator for infix strings with +, −, *, / and parentheses, using the usual precedence and left associativity. Hint: use shunting-yard to convert to postfix (before pushing an operator, pop every stacked operator of higher or equal precedence), then evaluate with a stack. Alternatively, write a recursive-descent parser with one function per precedence level.

<a id="94-spanning-trees"></a>

9.4 Spanning Trees

A spanning tree keeps a connected graph connected using as few edges as possible. This subchapter shows that spanning trees exist and counts them, builds them with DFS and BFS, uses the same depth-first idea to search solution spaces by backtracking, and finally finds spanning trees of minimum total weight with Prim's and Kruskal's algorithms.

Spanning Trees

Why. Many networks have redundant links on purpose, for reliability. Some tasks, however, need a loop-free backbone that still reaches everyone. Ethernet switches must forward broadcasts without circulating them forever (the Spanning Tree Protocol). A snow-plowing crew needs a minimal set of roads that keeps every town reachable. An algorithm may need a certificate that a graph is connected. In each case the answer is a spanning tree.

What. A spanning tree of a graph G is a subgraph that is a tree and contains every vertex of G.

Theorem. A graph has a spanning tree if and only if it is connected.

Proof. A spanning tree connects all vertices, so G must be connected. Conversely, if G is connected and has a cycle, remove one edge of that cycle. An edge on a cycle is not a bridge (8.3), so the graph stays connected. Repeat until no cycle remains. The result is connected, acyclic and contains every vertex. ∎

A disconnected graph has a spanning forest, with one spanning tree per component.

Consequences.

• Every spanning tree of a connected graph with n vertices has n − 1 edges (9.1). To reach one, you must delete exactly m − n + 1 edges. This number is the cyclomatic number (circuit rank) of the graph, and in general it is m − n + c for c components.
• Each edge e not in a spanning tree T closes exactly one cycle with T (characterization 6). These m − n + 1 fundamental cycles are the independent loops used in Kirchhoff's circuit laws, and they underlie cyclomatic complexity, the software metric.

Counting spanning trees: the matrix-tree theorem. Let L = D − A be the Laplacian of G (8.2), where D is the diagonal matrix of degrees and A the adjacency matrix. Kirchhoff's matrix-tree theorem says that the number of spanning trees τ(G) equals the determinant of L with any one row and the corresponding column deleted.

Graph	τ(G)
A tree	1
Cycle Cₙ	n (remove any one edge)
Complete graph Kₙ	n^{n−2} (Cayley's formula, 9.1)
Complete bipartite K_{m,n}	m^{n−1} · n^{m−1}
Hypercube Q₃	384

Example. The 4-cycle a, b, c, d plus the diagonal {a, c} has 5 edges. Choosing 3 of them gives C(5, 3) = 10 subsets. Exactly two of these subsets are the triangles abc and acd, which are cycles, so τ = 10 − 2 = 8.

       the graph             two of its 8 spanning trees

     a ─────── b           a ─────── b           a         b
     │ ╲       │           │                       ╲       │
     │   ╲     │           │                         ╲     │
     │     ╲   │           │                           ╲   │
     d ─────── c           d ─────── c           d ─────── c

from fractions import Fraction
from itertools import combinations

def det(M):
    """Exact determinant by Gaussian elimination over the rationals."""
    M = [[Fraction(x) for x in row] for row in M]
    n, result = len(M), Fraction(1)
    for col in range(n):
        pivot = next((r for r in range(col, n) if M[r][col] != 0), None)
        if pivot is None:
            return 0
        if pivot != col:
            M[col], M[pivot] = M[pivot], M[col]
            result = -result                               # a row swap flips the sign
        result *= M[col][col]
        for r in range(col + 1, n):
            factor = M[r][col] / M[col][col]
            for c in range(col, n):
                M[r][c] -= factor * M[col][c]
    return result

def spanning_tree_count(n, edges):
    L = [[0] * n for _ in range(n)]
    for u, v in edges:                                     # Laplacian L = D − A
        L[u][u] += 1
        L[v][v] += 1
        L[u][v] -= 1
        L[v][u] -= 1
    minor = [row[1:] for row in L[1:]]                     # delete row 0 and column 0
    return int(det(minor))

square_diag = [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)]
K5 = list(combinations(range(5), 2))
C6 = [(i, (i + 1) % 6) for i in range(6)]
K33 = [(i, j) for i in range(3) for j in range(3, 6)]
Q3 = [(u, u ^ (1 << b)) for u in range(8) for b in range(3) if u < u ^ (1 << b)]   # flip one bit
print([spanning_tree_count(n, E) for n, E in [(4, square_diag), (5, K5), (6, C6), (6, K33), (8, Q3)]])
# [8, 125, 6, 81, 384]

Key takeaways

• A spanning tree contains every vertex and is a tree. It exists exactly when the graph is connected.
• Building one means deleting m − n + 1 edges, one from each independent cycle.
• Every non-tree edge closes exactly one fundamental cycle with the tree.
• The matrix-tree theorem counts spanning trees with one determinant, and it reproduces Cayley's n^{n−2} for Kₙ.

Practice

1. (Beginner) Draw all 8 spanning trees of the 4-cycle with one diagonal. How many edges must be deleted from K₆ to leave a spanning tree?
2. (Intermediate) Count the spanning trees of K_{2,3} directly, by deciding which edges to leave out, and check the formula m^{n−1} · n^{m−1}. Then prove that τ(Cₙ) = n.
3. (Interview) A data center's Ethernet switches are connected with redundant links, and a broadcast packet loops forever and saturates the network. Explain how a spanning-tree protocol prevents this, and what should happen when an active link fails. Hint: elect a root switch, keep for each switch its shortest path toward the root (a BFS tree), and block every other port. When a link fails, recompute, and some blocked port becomes active again.

Constructing Spanning Trees with DFS and BFS

Why. The proof above deletes cycle edges one at a time, which is slow because each cycle must be found first. Building a tree up is far easier than cutting a graph down. A graph search adds exactly one edge for each newly discovered vertex, and those edges form a spanning tree. DFS and BFS (8.4) both do this in O(n + m) time, and the two trees they produce have very different shapes and uses.

What. Run DFS or BFS from any vertex s. Whenever a vertex w is discovered from a vertex u, keep the edge {u, w}. The kept edges are a DFS tree or a BFS tree rooted at s.

• Every vertex except s is discovered exactly once, so n − 1 edges are kept.
• Each kept edge joins a new vertex to the already discovered ones, so no cycle can form.
• So, by characterization 4, a search that reaches all vertices produces a spanning tree. If the search misses some vertices, G is disconnected. Restarting from an undiscovered vertex produces a spanning forest.

	DFS tree	BFS tree
Shape	Tall and thin	Short and bushy
Non-tree edges (undirected graph)	Always join an ancestor and a descendant (back edges)	Join vertices on the same level or on adjacent levels
Tree path from s to v	Arbitrary length	A shortest path (fewest edges)
Typical uses	Cycle detection, cut vertices and bridges, maze generation	Shortest-hop routing, Spanning Tree Protocol, bipartiteness

Example. Searching from a, with neighbors taken in alphabetical order:

      graph                   DFS tree from a              BFS tree from a

  a ─── b ─── c             a ─── b ─── c                a ─── b ─── c
  │     │     │                         │                │     │     │
  d ─── e ─── f             d ─── e ─── f                d     e     f
  │           │             │                            │
  g ───────── h             g ───────── h                g ───────── h

  n = 8, m = 10             depth 7: a Hamiltonian path  depth 3: levels {a}, {b, d}, {c, e, g}, {f, h}

Both trees have 7 edges, and in each case the 3 remaining edges are non-tree edges. In the DFS tree they are ad, be and fh, and each joins an ancestor to a descendant. In the BFS tree they are de, ef and fh, and each joins vertices on the same level or on adjacent levels.

from collections import deque

graph = {"a": "bd", "b": "ace", "c": "bf", "d": "aeg", "e": "bdf", "f": "ceh", "g": "dh", "h": "fg"}

def dfs_tree(adj, s):
    seen, edges = {s}, []
    def visit(u):
        for w in adj[u]:
            if w not in seen:
                seen.add(w)
                edges.append(u + w)                       # tree edge: w was discovered from u
                visit(w)
    visit(s)
    return edges

def bfs_tree(adj, s):
    seen, edges, queue = {s}, [], deque([s])
    while queue:
        u = queue.popleft()
        for w in adj[u]:
            if w not in seen:
                seen.add(w)
                edges.append(u + w)
                queue.append(w)
    return edges

print(dfs_tree(graph, "a"))   # ['ab', 'bc', 'cf', 'fe', 'ed', 'dg', 'gh']
print(bfs_tree(graph, "a"))   # ['ab', 'ad', 'bc', 'be', 'dg', 'cf', 'gh']

Key takeaways

• DFS and BFS build spanning trees in O(n + m) by keeping each discovery edge.
• A search that misses vertices proves the graph is disconnected. Restarting gives a spanning forest.
• DFS trees are deep, and every non-tree edge is a back edge. BFS trees are shallow, and they contain shortest paths from the root.
• The choice of tree depends on the job: structure (DFS) or distance (BFS).

Practice

1. (Beginner) Build the DFS and BFS trees of the example graph starting from e, with neighbors in alphabetical order. Mark the non-tree edges in each.
2. (Intermediate) Prove that in a BFS tree of an undirected graph, every non-tree edge joins vertices whose levels differ by at most 1, and that in a DFS tree every non-tree edge joins an ancestor and a descendant. Use these facts to explain why the DFS tree of the example graph is so much deeper than its BFS tree.
3. (Interview) Generate a random perfect maze on a W × H grid: every cell must be reachable from every other, by exactly one path. Hint: cells are vertices, neighboring cells are joined by edges, and a perfect maze is exactly a spanning tree of this grid graph. Run DFS with the neighbor order shuffled and remove the wall for every tree edge, or use a randomized Kruskal's algorithm. Compare the corridors the two methods produce.

Backtracking

Why. Many problems ask for an arrangement that satisfies constraints: placing n queens on a chessboard so that none attacks another, filling a Sudoku, coloring a graph with k colors (8.5), choosing a subset with a given sum, finding a Hamiltonian circuit (8.4). Brute force generates every complete candidate and tests it, which is hopeless: for 8 queens with one queen per row, there are 8⁸ ≈ 16.8 million candidates. Backtracking builds a candidate one choice at a time and abandons a partial candidate as soon as it cannot be completed, so it never generates the millions of candidates that extend a hopeless start.

What. Picture all possible choice sequences as a rooted tree, the state-space tree:

• the root is the empty partial solution,
• the children of a vertex extend its partial solution by one more choice, and
• the leaves are complete candidates or dead ends.

Backtracking is a depth-first search of this tree, generated on the fly, with a feasibility test at every vertex. If a partial solution already violates a constraint, its whole subtree is pruned: the search goes back to the parent and tries the next choice. The tree is never stored. Only the current path is, so the memory used is proportional to the depth.

How. Almost every backtracking algorithm has this shape:

def backtrack(partial):
    if is_complete(partial):
        report(partial)
        return
    for choice in candidates(partial):
        if is_feasible(partial, choice):          # prune: skip choices that already break a constraint
            partial.append(choice)
            backtrack(partial)
            partial.pop()                         # undo the choice: the "back" in backtracking

For optimization problems, branch and bound adds a second test: prune a vertex when an optimistic bound on any completion is no better than the best solution found so far.

Example: 4 queens. Place one queen per row, with the choice in row r being its column. A partial placement survives if no two queens share a column or a diagonal.

                                 [ ]
             ╱               ╱            ╲               ╲
          [0]             [1]             [2]             [3]
         ╱    ╲             │               │             ╱    ╲
    [0,2]    [0,3]        [1,3]           [2,0]      [3,0]    [3,1]
     dead      │            │               │          │        dead
            [0,3,1]      [1,3,0]         [2,0,3]    [3,0,2]
             dead           │               │         dead
                       [1,3,0,2]       [2,0,3,1]
                        solution        solution

The search visits 17 vertices instead of the 4⁴ = 256 complete candidates. The two solutions are mirror images of each other.

def n_queens(n):
    solutions, visited = [], 0
    cols, diag, anti = set(), set(), set()          # occupied columns, diagonals r − c, anti-diagonals r + c
    placement = []

    def place(r):
        nonlocal visited
        visited += 1                                # one vertex of the state-space tree
        if r == n:
            solutions.append(placement.copy())
            return
        for c in range(n):
            if c in cols or r - c in diag or r + c in anti:
                continue                            # prune: no solution extends this placement
            cols.add(c)
            diag.add(r - c)
            anti.add(r + c)
            placement.append(c)
            place(r + 1)
            placement.pop()                         # undo, then try the next column
            cols.remove(c)
            diag.remove(r - c)
            anti.remove(r + c)

    place(0)
    return solutions, visited

print(n_queens(4))                                  # ([[1, 3, 0, 2], [2, 0, 3, 1]], 17)
solutions, visited = n_queens(8)
print(len(solutions), visited, 8 ** 8)              # 92 2057 16777216

For 8 queens, the search visits 2,057 vertices of the state-space tree to find all 92 solutions, compared with 8⁸ = 16,777,216 complete candidates for brute force.

Key takeaways

• Backtracking is a DFS of the state-space tree of partial solutions, generated as it goes.
• A feasibility test at each vertex prunes entire subtrees, and that pruning is where all of its speed comes from.
• Undo every choice after its recursive call, so that the shared state again matches the current path.
• Memory is proportional to the depth of the tree, not to its size. Branch and bound extends the idea to optimization.

Practice

1. (Beginner) Use backtracking to find all subsets of {3, 5, 6, 7} that sum to 15. Draw the state-space tree (each level decides whether one element is included), and prune whenever the partial sum exceeds 15.
2. (Intermediate) Write a backtracking algorithm that decides whether a graph can be properly colored with k colors (8.5). Run it by hand on the wheel W₅ with k = 3 and with k = 4. Why does coloring the vertices in order of decreasing degree usually make the state-space tree much smaller?
3. (Interview) Write a Sudoku solver. Hint: keep sets of the digits already used in each row, column and box, so that each feasibility test is O(1). At each step, fill the empty cell with the fewest remaining candidates. This "most constrained first" rule prunes the tree dramatically, and a cell with zero candidates triggers an immediate backtrack.

Minimum Spanning Trees

Why. Suppose you must connect a set of towns with fiber, pipes or roads, and each possible link has a cost. Any spanning tree connects everything, but the costs of different spanning trees can vary enormously. A minimum spanning tree is the cheapest one. MSTs appear in network design, in clustering (group points by cutting the most expensive MST edges), in image segmentation, and in approximation algorithms: walking around an MST gives a traveling-salesperson tour at most twice the optimal length (8.4).

What. Let G be a connected, undirected graph with a weight w(e) on every edge. A minimum spanning tree (MST) is a spanning tree T that minimizes the total weight w(T) = Σ_{e ∈ T} w(e). A graph can have several MSTs, but if all edge weights are distinct, the MST is unique.

Two properties explain every MST algorithm. A cut is a partition of the vertices into two non-empty sets S and V − S. An edge crosses the cut if it has one endpoint on each side.

• Cut property. For any cut, a minimum-weight edge crossing it belongs to some MST. If it is the unique lightest crossing edge, it belongs to every MST. Proof (exchange argument). Let e = {u, v} be a lightest crossing edge, and let T be an MST that does not contain e. The path from u to v in T starts in S and ends outside it, so it uses some edge e' that also crosses the cut, and w(e') ≥ w(e). Then T + e − e' is a spanning tree with weight at most w(T), so it is also an MST, and it contains e. ∎
• Cycle property. For any cycle, a strictly heaviest edge on it belongs to no MST. If an MST contained it, removing it would split the tree into two parts, and some other edge of the cycle would reconnect them more cheaply.

The generic greedy algorithm. Start with no edges. Repeatedly add an edge that is lightest across some cut that no chosen edge crosses. By the cut property, the chosen edges always remain part of some MST. Prim's algorithm takes the cut "current tree versus everything else". Kruskal's algorithm takes the cut "one current component versus everything else".

An MST is not a shortest-path tree. Take a triangle with w(ab) = 2, w(bc) = 2 and w(ac) = 3. The MST is {ab, bc}, with weight 4. The shortest-path tree from a (Dijkstra, 8.4) is {ab, ac}, because the direct edge reaches c at cost 3 instead of 4. An MST minimizes the total cost of the network, while a shortest-path tree minimizes the distance from one source to each vertex.

Example. This graph is used for Prim's and Kruskal's algorithms as well. Its MST has weight 1 + 3 + 2 + 6 + 5 = 17:

  graph                                  MST (weight 17)

              4             6                              6
       A ─────────── B ─────────── C          A            B ─────────── C
       │           ╱ │             │          │          ╱ │             │
     1 │       3 ╱   │ 2           │ 5      1 │      3 ╱   │ 2           │ 5
       │       ╱     │             │          │      ╱     │             │
       │     ╱       │             │          │    ╱       │             │
       D ─────────── E ─────────── F          D            E             F
              7             8

from itertools import combinations

edges = [(4, "A", "B"), (6, "B", "C"), (1, "A", "D"), (3, "B", "D"),
         (2, "B", "E"), (5, "C", "F"), (7, "D", "E"), (8, "E", "F")]
V = "ABCDEF"

def is_spanning_tree(subset):
    comp = {v: v for v in V}                            # a minimal union–find
    def find(x):
        while comp[x] != x:
            x = comp[x]
        return x
    for _, u, v in subset:
        ru, rv = find(u), find(v)
        if ru == rv:
            return False                                # this edge closes a cycle
        comp[ru] = rv
    return True                                         # n − 1 edges and no cycle: a spanning tree (9.1)

trees = [t for t in combinations(edges, len(V) - 1) if is_spanning_tree(t)]
weight = lambda t: sum(w for w, _, _ in t)
best = min(trees, key=weight)
print(len(trees), sorted(map(weight, trees))[:4], max(map(weight, trees)))   # 29 [17, 18, 19, 20] 30   29 spanning trees, weighing 17 to 30
print(sorted(u + v for _, u, v in best), weight(best))  # ['AD', 'BC', 'BD', 'BE', 'CF'] 17

for k in range(1, len(V)):                              # check the cut property on every cut
    for S in combinations(V, k):
        crossing = [e for e in edges if (e[1] in S) != (e[2] in S)]
        assert min(crossing) in best                    # the lightest crossing edge is in the MST
print("cut property holds for all", 2 ** len(V) - 2, "choices of S")   # 62: each of the 31 cuts, seen from both sides

Key takeaways

• An MST is a spanning tree of minimum total weight. It is unique when all weights are distinct.
• Cut property: the lightest edge across any cut is safe to add. Cycle property: the heaviest edge on any cycle is never needed.
• Prim's and Kruskal's algorithms are two instances of the same greedy rule, with different choices of cut.
• An MST minimizes total cost, not the distances from a source. Do not confuse it with a shortest-path tree.

Practice

1. (Beginner) In the example graph, lower the weight of AB from 4 to 2.5. Use the cycle property on the cycle A, B, D to find which edge leaves the MST, and give the new total weight.
2. (Intermediate) Prove the cycle property carefully, and use the cut property to prove that the MST is unique when all edge weights are distinct.
3. (Interview) Given n points and their pairwise distances, split them into k clusters so that the smallest distance between two points in different clusters is as large as possible. Hint: run Kruskal's algorithm and stop when k components remain. Equivalently, delete the k − 1 heaviest edges of an MST. The cut property shows why no other clustering does better.

Prim's Algorithm

Why. Prim's algorithm grows a single tree outward from a starting vertex, always adding the cheapest edge that reaches a new vertex. This is how you would extend a network from a central office one connection at a time. It has the same structure as Dijkstra's algorithm (8.4), works directly on adjacency lists, and in its array version it is the method of choice for dense graphs.

What.

1. Start with a tree containing one vertex r and no edges.
2. Repeat n − 1 times: among all edges with exactly one endpoint in the tree, add a lightest one, together with its new endpoint.

Correctness. At every step, the chosen edge is a lightest edge across the cut (tree vertices, all other vertices), so by the cut property it is safe. After n − 1 steps the tree spans G.

How. A priority queue holds the candidate edges, keyed by weight.

• Lazy version: push every edge that leaves the newly added vertex. When a popped edge leads back into the tree, discard it. Each edge enters the heap at most twice, so this costs O(m log m) = O(m log n).
• Eager version: keep for each outside vertex v the value key[v], the weight of its lightest edge into the tree. Lower key[v] when a cheaper edge appears (decrease-key). With a binary heap this is O(m log n). With a plain array and a linear scan for the minimum, it is O(n²), which is optimal for dense graphs where m ≈ n².

	Prim	Dijkstra (8.4)
Grows	One tree from a start vertex	One tree from the source
Priority of an outside vertex v	min w(u, v) over tree vertices u	min dist(u) + w(u, v) over tree vertices u
Result	Minimum total weight	Shortest distance to each vertex
Negative weights	Fine	Not allowed

Example. Running Prim's algorithm from A on the graph above:

Step	Tree vertices	Candidate edges (weight)	Chosen
1	A	AB 4, AD 1	AD 1
2	A, D	AB 4, BD 3, DE 7	BD 3
3	A, B, D	BC 6, BE 2, DE 7	BE 2
4	A, B, D, E	BC 6, EF 8	BC 6
5	A, B, C, D, E	CF 5, EF 8	CF 5

Total weight: 1 + 3 + 2 + 6 + 5 = 17. The edge CF (weight 5) is chosen after BC (weight 6). Prim's algorithm adds edges in the order the tree reaches them, not in global order of weight.

import heapq

def prim(adj, start):
    in_tree, tree, total = {start}, [], 0
    heap = [(w, start, v) for v, w in adj[start]]       # edges leaving the current tree
    heapq.heapify(heap)
    while heap and len(in_tree) < len(adj):
        w, u, v = heapq.heappop(heap)
        if v in in_tree:
            continue                                     # stale entry: both endpoints are already in the tree
        in_tree.add(v)
        tree.append((u + v, w))
        total += w
        for x, wx in adj[v]:
            if x not in in_tree:
                heapq.heappush(heap, (wx, v, x))         # new candidates leaving the grown tree
    return tree, total

edges = [("A", "B", 4), ("B", "C", 6), ("A", "D", 1), ("B", "D", 3),
         ("B", "E", 2), ("C", "F", 5), ("D", "E", 7), ("E", "F", 8)]
adj = {v: [] for v in "ABCDEF"}
for u, v, w in edges:
    adj[u].append((v, w))
    adj[v].append((u, w))

print(prim(adj, "A"))   # ([('AD', 1), ('DB', 3), ('BE', 2), ('BC', 6), ('CF', 5)], 17)
print(prim(adj, "F"))   # ([('FC', 5), ('CB', 6), ('BE', 2), ('BD', 3), ('DA', 1)], 17)   same tree, different order

Key takeaways

• Prim's algorithm grows one tree, always adding the lightest edge that leaves it.
• It is correct by the cut property, applied to the cut (tree, rest).
• It costs O(m log n) with a binary heap, and O(n²) with an array, which is better for dense graphs.
• It has the same structure as Dijkstra's algorithm, with a different priority: the edge weight alone, not the distance from the source.

Practice

1. (Beginner) Run Prim's algorithm on the example graph starting from E. List the edges in the order they are added, and check that the total is 17.
2. (Intermediate) Implement the O(n²) array version of Prim's algorithm, with key[] and parent[] arrays and no heap. For which values of m, as a function of n, does it beat the binary-heap version?
3. (Interview) Minimum cost to connect all points. Given n points in the plane, where connecting two points costs their Manhattan distance, find the minimum total cost to connect all of them. Hint: the graph is complete and implicit, with about n²/2 edges. Do not build the edge list. Run the array version of Prim's algorithm, computing distances on the fly, in O(n²) time and O(n) memory.

Kruskal's Algorithm

Why. Kruskal's algorithm thinks globally instead of locally. Sort all the edges by weight and take the cheapest one that does not create a cycle, then the next, and so on. It is the natural choice when the graph is given as a list of edges, when the graph is sparse, or when you want the intermediate forests, which are exactly the clusterings used in single-linkage clustering.

What.

1. Sort the edges by weight, in increasing order.
2. Start with a forest of n single-vertex trees.
3. For each edge {u, v} in sorted order: if u and v are in different trees, add the edge, which merges the two trees. Otherwise skip it, because it would close a cycle.
4. Stop after n − 1 edges have been added.

Correctness. When the edge {u, v} is added, take the cut (the component of u, everything else). No lighter edge crosses this cut, since all lighter edges were already considered, and each one was either added or skipped because both its endpoints were in the same component. So {u, v} is a lightest crossing edge, and the cut property applies.

How. The test "are u and v in the same tree?" is answered by a union–find (disjoint-set) structure (2.5, 8.3). With union by size and path compression, each operation costs amortized O(α(n)), which is effectively constant. Sorting dominates, so the total is O(m log m) = O(m log n). If the edges are already sorted, or the weights are small integers that can be sorted in linear time, the rest is almost linear.

Example. Kruskal's algorithm on the graph above:

Edge	Weight	Action	Components afterwards
AD	1	Add	{A, D} {B} {C} {E} {F}
BE	2	Add	{A, D} {B, E} {C} {F}
BD	3	Add	{A, B, D, E} {C} {F}
AB	4	Skip: A and B are already in the same component	{A, B, D, E} {C} {F}
CF	5	Add	{A, B, D, E} {C, F}
BC	6	Add, and stop: 5 = n − 1 edges	{A, B, C, D, E, F}
DE, EF	7, 8	Never examined

Prim's and Kruskal's algorithms find the same tree here, because all the weights are distinct. With ties, they may return different MSTs of the same total weight.

class DisjointSet:
    def __init__(self, items):
        self.parent = {x: x for x in items}
        self.size = {x: 1 for x in items}

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]     # path halving keeps the trees shallow
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                                       # already in the same tree
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                                   # union by size: hang the smaller tree below
        self.size[ra] += self.size[rb]
        return True

def kruskal(vertices, edges):
    ds, tree = DisjointSet(vertices), []
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        if ds.union(u, v):                                     # endpoints were in different components
            tree.append((u + v, w))
            if len(tree) == len(vertices) - 1:
                break                                          # the forest has become a spanning tree
        else:
            print("skip", u + v, w)                            # this edge would close a cycle
    return tree, sum(w for _, w in tree)

edges = [("A", "B", 4), ("B", "C", 6), ("A", "D", 1), ("B", "D", 3),
         ("B", "E", 2), ("C", "F", 5), ("D", "E", 7), ("E", "F", 8)]
print(kruskal("ABCDEF", edges))
# skip AB 4
# ([('AD', 1), ('BE', 2), ('BD', 3), ('CF', 5), ('BC', 6)], 17)

	Prim's algorithm	Kruskal's algorithm
Intermediate state	One growing tree	A forest of merging trees
Next edge	Lightest edge leaving the tree	Globally lightest edge that joins two different trees
Data structure	Priority queue	Sorting plus union–find
Running time	O(m log n) with a heap, O(n²) with an array	O(m log m), dominated by sorting
Best suited to	Dense graphs, adjacency lists or matrices	Sparse graphs, edge lists, clustering
Disconnected input	Spans only the start vertex's component	Naturally returns a minimum spanning forest

Key takeaways

• Kruskal's algorithm takes edges in increasing order of weight, and skips any edge whose endpoints are already connected.
• It is correct by the cut property, applied to the component of one endpoint.
• Union–find makes the cycle test effectively O(1), so sorting dominates: O(m log m).
• Stopping when k components remain gives the maximum-spacing k-clustering. On a disconnected graph it returns a minimum spanning forest.

Practice

1. (Beginner) Run Kruskal's algorithm on K₄ with vertices 1, 2, 3, 4 and edge weights w(i, j) = i + j. Where does a tie appear, and do the two possible tie-breaks give different trees with the same total weight?
2. (Intermediate) Show that running Kruskal's algorithm with the edges in decreasing order of weight produces a maximum spanning tree. Then prove that for any two vertices, the path between them in a maximum spanning tree maximizes the smallest edge weight along the path (the "widest path", for example the maximum bandwidth between two routers).
3. (Interview) Optimize water distribution. Each of n houses can either get its own well, at cost well[i], or be connected by a pipe to another house, at cost pipe[i][j]. Find the minimum total cost to supply water to every house. Hint: add a virtual vertex 0 joined to each house i by an edge of weight well[i]. Building a well then becomes buying an edge to vertex 0, and the answer is the weight of an MST of the enlarged graph, computed with Kruskal's algorithm.

<a id="10-algorithms-and-complexity"></a>