Trees & Enumeration

Rooted Trees and Binary Trees

In Introduction to Graph Theory, we defined a tree as a connected acyclic graph and established that a tree on \(n\) vertices has exactly \(n - 1\) edges, with a unique path between any pair of vertices. We now impose additional structure by designating a special vertex as the root. The choice turns the tree from an undirected combinatorial object into a hierarchical, recursive data structure, which is one of the most pervasive abstractions in computer science.

Rooted Trees

Every non-root vertex has exactly one parent, and the root has no parent. The height of a rooted tree \((T, r)\) is the maximum depth over all vertices: \[ h(T) = \max_{v \in V} \operatorname{depth}(v). \] A rooted tree of height \(h\) has at least \(h + 1\) vertices (a path from root to deepest leaf) and the root sits at depth \(0\).

Binary Trees

The distinction between left and right matters. A single left child produces a different binary tree from a single right child, even though the underlying unrooted graph is the same. This ordered structure is what makes binary trees the natural setting for divide-and-conquer algorithms, where a problem splits into two subproblems at every step.

A binary tree is called height-balanced (or AVL-balanced) if for every vertex, the heights of its left and right subtrees differ by at most one (the empty tree is assigned height \(-1\)). A height-balanced binary tree on \(n\) vertices has height \(\Theta(\log n)\). The lower bound \(h \geq \lceil \log_2(n+1) \rceil - 1\) follows because at depth \(d\) there are at most \(2^d\) vertices, which gives \(n \leq 2^{h+1} - 1\). The upper bound \(h = O(\log n)\) follows from the balance condition, which forces the number of vertices to grow at least exponentially with height.

More precisely, the minimum number \(N(h)\) of vertices in a height-balanced tree of height \(h\) satisfies the Fibonacci-like recurrence \[ N(h) = N(h-1) + N(h-2) + 1 \] with \(N(0) = 1\) and \(N(1) = 2\). Indeed, in a smallest such tree one subtree of the root has height \(h - 1\) and the other has height at least \(h - 2\) by the balance condition. Minimality forces both subtrees to be smallest trees of their heights, the second of height exactly \(h - 2\). This yields \(N(h) \geq \varphi^h - 1\), where \(\varphi = (1 + \sqrt{5})/2\). Hence \(h \leq \log_\varphi(n + 1) = O(\log n)\).

Spanning Trees

So far we have studied trees as hierarchical structures, rooted and with a clear parent-child directionality. But trees serve a second, equally fundamental role: as the minimal connected skeleton of an arbitrary graph. A communication network, for instance, may contain many redundant links. Stripping away edges until no cycles remain, while preserving connectivity, yields a tree that spans the entire network. This shift in perspective, from rooted hierarchy to unrooted backbone, leads to the concept of a spanning tree.

Recall from Introduction to Graph Theory that a spanning subgraph of \(G = (V, E)\) is a subgraph that contains all vertices of \(G\).

The number of spanning trees of a graph is a fundamental invariant. We will return to this question at the end of this page with Cayley's formula for complete graphs, and later with Kirchhoff's matrix tree theorem in the study of graph Laplacians.

Binary Search Trees and the Comparison Model

We now turn from the structure of binary trees to their use as a data structure for maintaining ordered data. The binary search tree imposes an ordering invariant that enables efficient search, insertion, and deletion. The analysis of its worst case leads us naturally to the comparison model and a fundamental information-theoretic limit on sorting.

Binary Search Trees

The BST property is an invariant maintained across all operations. An inorder traversal of a BST visits the keys in sorted order. In effect, the tree is a spatial encoding of a sorted sequence. Search proceeds by comparing the target key with the current node and recursing into the appropriate subtree.

The crux is the height problem. The height of a BST on \(n\) keys ranges from \(\Theta(\log n)\) (balanced) to \(\Theta(n)\) (a degenerate single chain). Inserting keys \(1, 2, 3, \ldots, n\) in order produces the degenerate case where every node has only a right child, and search degrades to linear scan. Self-balancing BSTs solve this problem by performing rotations during insertion and deletion to maintain \(O(\log n)\) height. Examples are AVL trees, which enforce a height-balance condition at every node, and Red-Black trees, which enforce coloring invariants that guarantee \(h \leq 2 \log_2(n+1)\).

The Decision Tree Model

We now shift perspective. Rather than analyzing a specific data structure, we ask what any algorithm can achieve under a natural computational constraint.

Any comparison-based sorting algorithm on \(n\) elements can be modeled by a decision tree, a binary tree in which each internal node represents a comparison "\(a_i \leq a_j\)?", with the left child corresponding to "yes" and the right child to "no". Each leaf represents a specific permutation of the input, namely the algorithm's output on that execution path. Since the algorithm must produce the correct sorted output for every one of the \(n!\) input permutations, distinct input permutations must reach distinct leaves. Hence the decision tree has at least \(n!\) leaves.

This lower bound is tight. Merge sort achieves \(O(n \log n)\) comparisons in every case, and is therefore optimal in the comparison model. Quicksort achieves \(O(n \log n)\) in expectation (over random pivot choices) but \(O(n^2)\) in the worst case. Heapsort also achieves \(O(n \log n)\) worst-case while sorting in place, by exploiting the binary heap, a tree-based data structure defined next.

The completeness condition forces the height of an \(n\)-vertex heap to be \(\lfloor \log_2 n \rfloor\). Insertion and extract-min are implemented by sift-up and sift-down along a single root-to-leaf path, so both run in \(O(\log n)\) time.

The heap is the standard implementation of the priority queue abstract data type. The same structure powers Dijkstra's algorithm in Network Flow & Walks on Graphs, where it enables efficient extraction of the vertex with minimum tentative distance.

Beyond Comparisons

The \(\Omega(n \log n)\) barrier is a statement about the comparison model, not about sorting in general. Algorithms that exploit the internal structure of keys can escape this bound entirely. Counting sort sorts \(n\) integers in the range \(\{0, 1, \ldots, k\}\) in \(O(n + k)\) time by using direct addressing. It allocates an array of size \(k + 1\), counts occurrences, and reads off the sorted output. Radix sort extends this to \(d\)-digit keys by applying counting sort to each digit position, achieving \(O(d(n + k))\). These algorithms do not compare pairs of elements, so they bypass the decision tree model entirely.

Counting Trees: Catalan and Schröder Numbers

We have seen that binary trees, BSTs, and decision trees are ubiquitous computational structures. A natural question arises: how many distinct binary trees are there on \(n\) nodes? The answer leads us to the Catalan numbers, one of the most celebrated sequences in combinatorics, and reveals deep connections between tree enumeration, lattice paths, and generating functions. The tools here build directly on the counting principles and binomial coefficients developed in Introduction to Combinatorics.

The Catalan Numbers

The recursive structure of binary trees yields a recurrence that determines the entire sequence from the base case \(C_0 = 1\).

The Generating Function

Define the ordinary generating function \[ C(u) = \sum_{n=0}^{\infty} C_n \, u^n. \]

The Catalan recurrence \(C_{n+1} = \sum_{i=0}^{n} C_i \, C_{n-i}\) is a convolution. By the definition of formal power series multiplication, the right-hand side is the coefficient of \(u^n\) in the product \(C(u) \cdot C(u) = C(u)^2\). Hence \(\sum_{n=0}^{\infty} C_{n+1} u^n = C(u)^2\). The left-hand side equals \(\bigl(C(u) - C_0\bigr)/u = \bigl(C(u) - 1\bigr)/u\). Equating the two expressions, we obtain \[ \frac{C(u) - 1}{u} = C(u)^2 \quad \implies \quad u \, C(u)^2 - C(u) + 1 = 0. \]

This is a quadratic equation in \(C(u)\). Multiplying it by \(4u\) and completing the square, we obtain \[ \bigl(1 - 2u\, C(u)\bigr)^2 = 1 - 4u. \] A formal power series with constant term \(1\) has exactly one square root with constant term \(1\). Indeed, if \(f^2 = g^2\) and both \(f\) and \(g\) have constant term \(1\), then \((f - g)(f + g) = 0\), and \(f + g\) is invertible because its constant term is \(2\). We write \(\sqrt{1 - 4u}\) for this square root of \(1 - 4u\). Since \(1 - 2u\, C(u)\) has constant term \(1\), it equals \(\sqrt{1 - 4u}\). The series \(1 - \sqrt{1 - 4u}\) has zero constant term and is therefore divisible by \(u\), so we can solve for \(C(u)\):

The first few coefficients of the right-hand side, expanded as a power series in \(u\), are \[ \frac{1 - \sqrt{1 - 4u}}{2u} = 1 + u + 2u^2 + 5u^3 + 14u^4 + 42u^5 + \cdots, \] which recovers the Catalan sequence.

The Closed Form via the Reflection Principle

We now derive the closed-form expression \(C_n = \frac{1}{n+1}\binom{2n}{n}\) using a bijection between binary trees and lattice paths, combined with the reflection principle.

Bijection: binary trees \(\leftrightarrow\) Dyck paths. We define a recursive encoding. Given a binary tree \(T\) on \(n\) nodes with root \(r\), left subtree \(L\), and right subtree \(R\), encode \(T\) as \[ \texttt{encode}(T) = \text{"("} \cdot \texttt{encode}(L) \cdot \text{")"} \cdot \texttt{encode}(R), \] with the empty tree mapping to the empty string. Each node contributes exactly one "(" and one ")", so the result is a string of length \(2n\). Interpreting "(" as an up-step and ")" as a down-step yields a path with \(n\) up-steps and \(n\) down-steps. It is a Dyck path of length \(2n\), since it never dips below the \(x\)-axis. We check this by induction on \(n\). Suppose every prefix of \(\texttt{encode}(L)\) and of \(\texttt{encode}(R)\) has at least as many "(" as ")". A prefix of \(\texttt{encode}(T)\) that ends inside the block "(" \(\cdot\) \(\texttt{encode}(L)\) \(\cdot\) ")" has one more "(" than the corresponding prefix of \(\texttt{encode}(L)\). The block itself is balanced, and a longer prefix only appends a prefix of \(\texttt{encode}(R)\).

The encoding is invertible. When we scan the string from left to right, the first "(" corresponds to the root, the balanced substring immediately following it encodes \(L\), the matching ")" closes the root, and the remaining substring encodes \(R\). This matching ")" is the first return of the path to the \(x\)-axis, and every nonempty Dyck path splits uniquely at its first return in this way. Decoding is therefore defined on every Dyck path, and by induction on \(n\) the two maps are mutually inverse.

Read as a string of parentheses, the encoding is a sequence of \(n\) pairs of balanced parentheses. The correspondence up = "(", down = ")" thus identifies binary trees, Dyck paths, and balanced parenthesizations as three views of the same object.

The reflection principle exemplifies a powerful pattern in enumerative combinatorics: counting hard-to-describe objects (here, Dyck paths) through their complement. The complement (here, the bad paths) is put in bijection with objects of an easily counted type, and the rule of sum applied to the partition of all paths into good and bad ones gives the count.

Schröder Numbers and Lattice Path Generalizations

The Catalan numbers count lattice paths with two types of steps: up \((1, +1)\) and down \((1, -1)\). A natural generalization is to allow a third type of step.

The number of Schröder paths of semilength \(n\) (that is, from \((0,0)\) to \((2n,0)\)) is the large Schröder number \(S_n\), and the number of small Schröder paths is the little Schröder number (or super Catalan number) \(s_n\). Their initial values are \[ \begin{align*} S_n &\colon 1,\, 2,\, 6,\, 22,\, 90,\, 394,\, \ldots \\\\ s_n &\colon 1,\, 1,\, 3,\, 11,\, 45,\, 197,\, \ldots \end{align*} \]

One observes that \(S_n = 2\, s_n\) for \(n \geq 1\). The distinction is that large Schröder paths permit flat steps on the \(x\)-axis while small Schröder paths forbid them. The precise factor of 2 can be established by a decomposition argument at the first return to the \(x\)-axis.

In terms of tree enumeration, the little Schröder numbers \(s_n\) count plane trees (ordered rooted trees where each internal vertex has \(\geq 2\) children) on \(n + 1\) leaves. For instance, \(s_2 = 3\) counts the three plane trees with 3 leaves: the root with 3 children (all leaves), and the two trees where the root has 2 children with one being an internal node bearing 2 leaves. A binary tree, the object counted by \(C_n\), gives every node exactly 2 child slots, possibly empty. The little Schröder numbers count the more general case in which each internal node may have 2, 3, or more children.

For \(n \geq 1\), the large Schröder numbers satisfy the recurrence \[ \begin{align*} (n+2)\, S_{n+1} &= 3(2n+1)\, S_n - (n-1)\, S_{n-1}, \\\\ S_0 &= 1, \\\\ S_1 &= 2, \end{align*} \] as well as a convolution-type recurrence that mirrors the Catalan case: \[ S_{n+1} = S_{n} + \sum_{k=0}^{n} S_k \, S_{n-k}, \quad S_0 = 1. \] The additional \(S_n\) term (compared to the pure convolution \(C_{n+1} = \sum C_k C_{n-k}\)) reflects the extra flat step available in Schröder paths. Both recurrences can be derived from the generating function \(S(u) = (1 - u - \sqrt{1 - 6u + u^2})/(2u)\). We state them without proof, since the Schröder numbers play only a supporting role on this page.

The Motzkin Numbers

Between Dyck paths and Schröder paths lies a third family. A Motzkin path of length \(n\) is a lattice path from \((0,0)\) to \((n, 0)\) using up-steps \((1,+1)\), down-steps \((1,-1)\), and horizontal steps \((1, 0)\), that never passes below the \(x\)-axis. The number of Motzkin paths of length \(n\) is the Motzkin number \(M_n\): \[ M_n \colon 1,\, 1,\, 2,\, 4,\, 9,\, 21,\, 51,\, \ldots \] In terms of trees, \(M_n\) counts the number of ordered trees on \(n+1\) vertices where each internal vertex has either one or two children (unary-binary trees). This positions the three families in a natural hierarchy:

• Catalan \(C_n\): binary trees on \(n\) nodes, in which each internal node has at most 2 children, distinguished as left and right.
• Motzkin \(M_n\): unary-binary trees with \(n\) edges, in which each internal node has 1 or 2 children.
• Little Schröder \(s_n\): plane trees with \(n+1\) leaves, in which each internal node has \(\geq 2\) children.

Labeled Trees: Cayley's Formula

The Catalan and Schröder numbers count unlabeled trees, that is, structures considered up to isomorphism. We now ask a different question: given a fixed vertex set \(\{1, 2, \ldots, n\}\), how many distinct labeled trees can be formed? Equivalently, how many spanning trees does the complete graph \(K_n\) have? The answer, due to Cayley, is a single power of \(n\).

For \(n = 2\) there is \(2^0 = 1\) tree, the single edge \(12\). For \(n = 3\) there are \(3^1 = 3\) trees, the star graphs centered at each vertex. For \(n = 4\) there are \(4^2 = 16\) labeled trees.

We prove Cayley's formula by exhibiting a bijection between labeled trees on \([n]\) and sequences in \([n]^{n-2}\), known as Prüfer sequences.

Prüfer Sequences

Encoding: labeled tree \(\to\) Prüfer sequence. Given a labeled tree \(T\) on \([n]\):

1. Find the leaf with the smallest label. Call it \(\ell\).
2. Record the label of the unique neighbor of \(\ell\). This is the first entry \(a_1\) of the Prüfer sequence.
3. Remove \(\ell\) and its incident edge from \(T\).
4. Repeat steps 1-3 on the resulting tree with \(n - 1\) vertices, recording \(a_2\), then \(a_3\), and so on.
5. Stop after \(n - 2\) iterations. At this point, exactly 2 vertices remain (connected by a single edge).

Decoding: Prüfer sequence \(\to\) labeled tree. Given a Prüfer sequence \((a_1, a_2, \ldots, a_{n-2})\):

1. Initialize a degree counter: set \(d(v) = 1 + (\text{number of times } v \text{ appears in the sequence})\) for each \(v \in [n]\).
2. For \(i = 1, 2, \ldots, n-2\): find the smallest \(v \in [n]\) with \(d(v) = 1\), and call it \(v_i\). Add edge \(\{v_i, a_i\}\) to the tree. Decrement \(d(v_i)\) and \(d(a_i)\) by 1.
3. After processing all entries, exactly two vertices have \(d(v) = 1\). Connect them with the final edge.

The encoding and decoding procedures are mutual inverses, establishing a bijection between labeled trees on \([n]\) and sequences in \([n]^{n-2}\). Verifying this rests on a few elementary observations.

• Encoding is well-defined. At each iteration, the current tree has at least 2 leaves, so the smallest leaf is unambiguously chosen. Any tree on \(\geq 2\) vertices has at least 2 leaves. Indeed, a tree on \(n\) vertices has \(n - 1\) edges, so counting each edge from both endpoints gives \(\sum_v \deg(v) = 2(n-1)\). Since a tree on \(n \geq 2\) vertices is connected, every vertex has degree at least 1. If at most one vertex had degree 1, the sum would be at least \(1 + 2(n-1) = 2n - 1 \gt 2(n-1)\), a contradiction. Removing a leaf preserves the tree property, so the procedure runs for exactly \(n - 2\) steps.
• Decoding is well-defined. Call a vertex processed once it has been chosen as some \(v_j\). Its counter then drops to \(0\), so it is never chosen again. The degree counter maintains the invariant that at the start of step \(i\), for each unprocessed vertex \(v\), \[ d(v) = 1 + \#\{j \geq i : a_j = v\}, \] verifiable by induction on \(i\). In particular, every \(a_j\) with \(j \geq i\) is unprocessed, since a processed vertex had counter \(1\) and hence no later occurrence. Summing over the \(n - i + 1\) unprocessed vertices gives \(\sum d(v) = (n - i + 1) + (n - 1 - i) = 2(n - i)\). Since this is strictly less than \(2(n - i + 1)\), some unprocessed vertex must have \(d(v) = 1\). The smallest such vertex is unambiguously chosen. The resulting graph collects \(n - 1\) edges on \(n\) vertices, and it is acyclic by the following component invariant. At the start of each step, the connected component of any unprocessed vertex \(v\) contains only \(v\) among the unprocessed vertices, since its other members are previously processed vertices \(v_j\) (by induction on the step index). Hence \(v_i\) and \(a_i\) lie in different components when edge \(\{v_i, a_i\}\) is added, so every edge of the constructed graph, including the final edge between the two survivors, is a bridge, and the graph is a forest. With \(n - 1\) edges on \(n\) vertices, it is in fact a tree.
• The two procedures are inverse. Both rest on one fact. By the vertex-frequency property proved below, a vertex of the current tree is a leaf exactly when it does not occur among the remaining entries of the sequence, which is the decoder's condition \(d(v) = 1\). So when decoding is applied to the sequence of \(T\), the vertex \(v_i\) chosen at step \(i\) is the leaf that the encoder removed at step \(i\), the edge \(\{v_i, a_i\}\) is the edge the encoder deleted, and the final edge joins the two vertices the encoder left. Decoding therefore returns \(T\). Conversely, in the tree decoded from \((a_1, \ldots, a_{n-2})\), the degree of an unprocessed vertex at step \(i\) is exactly its counter \(d(v)\), so the encoder removes the same vertices \(v_1, v_2, \ldots\) in the same order and records \(a_1, a_2, \ldots\) again.

The vertex-frequency property states that a vertex \(v\) appears in the Prüfer sequence of \(T\) exactly \(\deg_T(v) - 1\) times. Indeed, \(v\) is recorded as the neighbor of a removed leaf precisely when one of its incident edges is deleted. Each such deletion reduces \(\deg(v)\) by 1, and the process terminates with \(v\) either still present (when \(\deg_T(v) - 1\) of its edges have been removed) or having become itself a leaf and been removed (recording its own neighbor, not \(v\) itself). In both cases \(v\) is recorded \(\deg_T(v) - 1\) times. In particular, leaves never appear in the sequence, and the two vertices remaining at the end are those whose degree counter has been decremented to 1 after all entries are processed.

The decoding implementation runs in \(O(n \log n)\) using a priority queue (or \(O(n)\) with a more careful implementation that scans the sequence once to compute final degree counts).

The vertex-frequency property reduces the counting of trees with a prescribed degree sequence to a problem about arrangements of symbols in a sequence.

Cayley's formula counts the spanning trees of the complete graph \(K_n\), in which every pair of distinct vertices is adjacent (see Introduction to Graph Theory). It has \(\binom{n}{2}\) edges, and Cayley's formula tells us that \(n^{n-2}\) of its \(\binom{\binom{n}{2}}{n-1}\) spanning subgraphs with \(n - 1\) edges are trees.