Trees

Definition

A tree is a connected acyclic (no cycles) graph.

Equivalent Characterizations

For a graph $G$ with $n$ vertices, the following are equivalent:

1. $G$ is a tree (connected and acyclic)
2. $G$ is connected with exactly $n - 1$ edges
3. $G$ is acyclic with exactly $n - 1$ edges
4. Any two vertices are connected by a unique path
5. $G$ is connected, but removing any edge disconnects it
6. $G$ is acyclic, but adding any edge creates exactly one cycle

Basic Properties

Edge Count

$|E| = |V| - 1$

Leaves

Every tree with $n \geq 2$ vertices has at least 2 leaves (degree-1 vertices).

Proof: Sum of degrees = $2|E| = 2(n-1)$. Average degree $< 2$, so some vertices have degree 1.

Subtrees

Removing an edge from a tree creates two smaller trees (or one tree if leaf removed).

Rooted Trees

A rooted tree designates one vertex as the root.

Terminology

Term	Definition
Root	Designated starting vertex
Parent of $v$	Unique vertex on path from $v$ to root (if $v$ is not root)
Child of $v$	Vertex whose parent is $v$
Ancestor	Vertex on path from $v$ to root
Descendant	Vertex for which $v$ is an ancestor
Sibling	Vertices with the same parent
Leaf	Vertex with no children
Internal vertex	Vertex with at least one child
Depth of $v$	Length of path from root to $v$
Height	Maximum depth of any vertex
Level $k$	Set of vertices at depth $k$

Binary Trees

Each internal vertex has at most 2 children (left and right).

Types

Full Binary Tree: Every internal vertex has exactly 2 children.

Perfect Binary Tree: Full binary tree where all leaves are at the same depth.

Complete Binary Tree: All levels except possibly the last are full; last level filled left-to-right.

Properties

For a full binary tree with $i$ internal vertices and $l$ leaves:

• Total vertices: $n = i + l = 2i + 1$
• Leaves: $l = i + 1$

For a perfect binary tree of height $h$:

• Vertices: $2^{h+1} - 1$
• Internal vertices: $2^h - 1$
• Leaves: $2^h$

Spanning Trees

A spanning tree of a connected graph $G$ is a subgraph that:

• Is a tree
• Contains all vertices of $G$

Existence

Every connected graph has at least one spanning tree.

Finding Spanning Trees

BFS: Produces spanning tree with shortest paths from root.

DFS: Produces spanning tree with deep branches.

Number of Spanning Trees

Cayley's Formula: The complete graph $K_n$ has $n^{n-2}$ labeled spanning trees.

Matrix Tree Theorem: Number of spanning trees equals any cofactor of the Laplacian matrix.

For the cycle $C_n$: exactly $n$ spanning trees.

Minimum Spanning Trees

For a weighted connected graph, a minimum spanning tree (MST) has minimum total edge weight.

Kruskal's Algorithm

1. Sort edges by weight
2. Add edges in order, skipping those that create cycles
3. Stop when $n - 1$ edges added

Time: $O(|E| \log |E|)$

Prim's Algorithm

1. Start with any vertex
2. Repeatedly add the minimum-weight edge connecting tree to non-tree vertex
3. Stop when all vertices included

Time: $O(|E| \log |V|)$ with binary heap

Properties

• MST is unique if all edge weights are distinct
• Cut property: Minimum edge crossing any cut is in some MST
• Cycle property: Maximum edge in any cycle is not in some MST

Tree Traversals

Preorder

Visit root, then recursively visit children (left to right).

Inorder (Binary Trees)

Visit left subtree, root, then right subtree.

Postorder

Recursively visit children, then visit root.

Level Order (BFS)

Visit vertices level by level, left to right.

Applications

Expression Trees

Binary tree representing mathematical expressions.

• Leaves: operands
• Internal vertices: operators
• Inorder: infix notation
• Preorder: prefix notation
• Postorder: postfix notation

Huffman Trees

Binary tree for optimal prefix codes.

• More frequent symbols: shorter codes
• Less frequent: longer codes

Binary Search Trees

• Left child $<$ parent $<$ right child
• Search, insert, delete: $O(h)$ where $h$ is height
• Balanced variants: AVL, Red-Black: $O(\log n)$

Prüfer Sequences

A Prüfer sequence is a unique $(n-2)$-length sequence of vertex labels that encodes a labeled tree on $n$ vertices.

Tree to Prüfer Sequence

1. Find the leaf with smallest label
2. Add its neighbor's label to the sequence
3. Remove the leaf
4. Repeat until 2 vertices remain

Prüfer Sequence to Tree

Reconstructs the original tree.

Consequence

Bijection between labeled trees on $n$ vertices and sequences of length $n - 2$ from $\{1, \ldots, n\}$.

Number of labeled trees: $n^{n-2}$ (Cayley's formula)