Trees

A tree is a connected, acyclic undirected graph. Trees are the most important graphs in computer science: file systems, parse trees, decision trees, search trees, heaps, tries.

#Equivalent characterisations

For a graph T with n vertices, these are all equivalent — any one of them makes T a tree:

1. T is connected and has no cycles.
2. There is a unique simple path between every pair of vertices.
3. T is connected and has exactly n − 1 edges.
4. T has no cycles and has exactly n − 1 edges.
5. T is connected, but removing any edge disconnects it (every edge is a bridge).
6. T has no cycles, but adding any edge creates exactly one cycle.

A graph with no cycles that may be disconnected is a forest — a collection of trees. A forest with n vertices and c components has n − c edges.

#Rooted and m-ary trees

Choosing one vertex as the root gives every edge a direction away from it, with the usual parent, child, leaf, level and height terms (see Trees & Binary Trees in Data Structures).

An m-ary tree gives each internal vertex at most m children; a full m-ary tree gives each internal vertex exactly m children.

An m-ary tree of height h has at most mʰ leaves, so a tree with l leaves has height at least ⌈log_m l⌉.

def full_mary(m, internal):
    n = m * internal + 1
    leaves = (m - 1) * internal + 1
    return n, leaves

# A knockout chess tournament: each match (internal vertex) has 2 players (children)
players = 64
matches = (players - 1) // (2 - 1)
print(f"{players} players need {matches} matches")
print("full ternary tree with 10 internal vertices (vertices, leaves):", full_mary(3, 10))

# Chain letter: each person sends to 4 others; 100 people never send (leaves)
m, l = 4, 100
print(f"people involved: {(m * l - 1) // (m - 1)}, senders: {(l - 1) // (m - 1)}")

64 players need 63 matches
full ternary tree with 10 internal vertices (vertices, leaves): (31, 21)
people involved: 133, senders: 33

#Spanning trees

A spanning tree of a connected graph G is a subgraph that is a tree and includes every vertex of G. Every connected graph has one (delete cycle edges until none are left); BFS and DFS each produce one. With weights, the cheapest is the minimum spanning tree — Kruskal and Prim.

Cayley's formula: the complete graph Kₙ has nⁿ⁻² different spanning trees (equivalently, there are nⁿ⁻² labelled trees on n vertices). K₄ has 4² = 16.

from itertools import combinations

def is_tree(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return False          # a cycle
        parent[ru] = rv
    return len(edges) == n - 1    # n - 1 edges and no cycle: connected tree

for n in range(2, 6):
    all_edges = list(combinations(range(n), 2))
    count = sum(1 for es in combinations(all_edges, n - 1) if is_tree(n, es))
    print(f"K{n}: {count} spanning trees, Cayley n^(n-2) = {n ** (n - 2)}")

K2: 1 spanning trees, Cayley n^(n-2) = 1
K3: 3 spanning trees, Cayley n^(n-2) = 3
K4: 16 spanning trees, Cayley n^(n-2) = 16
K5: 125 spanning trees, Cayley n^(n-2) = 125

#Prefix codes and decision trees

• Binary trees whose leaves are symbols give prefix codes — the basis of Huffman coding.
• A decision tree for sorting n items has n! leaves, so its height (worst-case comparisons) is at least log₂(n!) = Ω(n log n) — the proof that comparison sorting cannot beat O(n log n).