Trees - Definition and Characterizations

Trees are among the most fundamental and well-studied structures in graph theory, appearing throughout mathematics and computer science as hierarchical data structures, parse trees, decision trees, and network designs.

DefinitionTree

A tree is a connected acyclic graph. Equivalently, a tree is a connected graph with no cycles. A forest is an acyclic graph (possibly disconnected), i.e., a disjoint union of trees.

A leaf is a vertex of degree 1. An internal vertex has degree at least 2.

Trees admit numerous equivalent characterizations, each revealing different structural properties and providing different proof techniques.

TheoremCharacterizations of Trees

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

$T$ is a tree (connected and acyclic)
$T$ is connected and has $n-1$ edges
$T$ is acyclic and has $n-1$ edges
$T$ is minimally connected (removing any edge disconnects $T$ )
$T$ is maximally acyclic (adding any edge creates exactly one cycle)
Every pair of vertices in $T$ is connected by a unique path

ExampleComplete Binary Tree

A complete binary tree of height $h$ has $n = 2^{h+1} - 1$ vertices and $m = 2^{h+1} - 2 = n-1$ edges. Each internal vertex has degree 3 (except the root with degree 2), and there are $2^h$ leaves at level $h$ . This structure is fundamental in data structures and algorithms.

DefinitionRooted Tree

A rooted tree is a tree with one distinguished vertex called the root. For any vertex $v$ , the parent is the unique neighbor closer to the root, and children are neighbors farther from the root. The height is the maximum distance from root to any vertex.

A binary tree is a rooted tree where each vertex has at most two children (often labeled left and right).

Remark

Every tree with $n \geq 2$ vertices has at least two leaves. This follows because the sum of degrees $2(n-1) = 2n - 2$ distributed among $n$ vertices requires at least two vertices of degree 1 if the tree is connected.

DefinitionTree Traversals

For rooted trees, three standard traversal orders are:

Preorder: Visit root, then recursively traverse subtrees
Inorder (binary trees): Traverse left subtree, visit root, traverse right subtree
Postorder: Recursively traverse subtrees, then visit root

These traversals have complexity $O(n)$ and are fundamental to tree algorithms.

Trees provide optimal connectivity with minimal edges, making them essential for network design, spanning tree protocols in computer networks, and minimum cost connectivity problems.