In graph theory, a tree is an undirected graph that is connected and contains no cycles. Equivalently, exactly one simple path joins any two of its vertices. A tree therefore represents connectivity without redundant routes: removing any edge disconnects it, while adding an edge between two previously nonadjacent vertices creates exactly one cycle. A graph whose connected components are trees is called a forest.
Trees are central to combinatorics and computer science because they combine a simple global structure with considerable expressive power. They describe branching relationships, organize data, support efficient algorithms, and provide minimal networks connecting specified vertices. They also occur within more complicated graphs as spanning trees and as the organizing structures of graph decompositions. Their theory includes exact counting formulas, matrix identities, geometric properties, and extensions to infinite graphs.
Definition and equivalent characterizations
Unless otherwise stated, a tree is a simple, undirected graph , where is a nonempty set of vertices and is a set of unordered pairs of distinct vertices. A simple path visits no vertex more than once, and a cycle is a closed path with no repeated vertices other than its common starting and ending vertex. Connectivity means that every pair of vertices can be joined by a finite path. The graph consisting of one vertex and no edges is a tree. The graph with no vertices is usually excluded, although conventions vary in contexts involving recursive constructions.
For a finite simple graph with vertices, the following conditions are equivalent:
- The graph is connected and has no cycles.
- There is exactly one simple path between each pair of distinct vertices.
- The graph is connected and has edges.
- The graph has no cycles and has edges.
- The graph is connected, and removing any edge disconnects it.
- The graph has no cycles, but adding any missing edge creates a cycle.
These equivalences express two complementary extremal properties. A tree is minimally connected, because no edge can be deleted without losing connectivity, and maximally acyclic, because no additional edge can be inserted without introducing a cycle. Neither phrase means that the tree is uniquely determined by its vertex set: many different trees can have the same vertices.
The unique-path characterization follows directly from the definition. Connectivity supplies at least one path between two vertices. If two distinct simple paths existed, their divergence and subsequent reunion would contain a cycle. Conversely, vertices on a cycle are connected by two different routes around it, so uniqueness rules out cycles. This argument is also an example of mathematical proof by extracting a forbidden configuration from a hypothetical alternative.
The formula can be established using mathematical induction. Every finite tree with at least two vertices has a vertex incident with exactly one edge. Removing that vertex and its incident edge leaves a smaller tree. Repeating the process reduces the graph to one vertex and proves the formula. More generally, a finite forest with vertices and connected components has edges.
The edge-count conditions require finiteness. For infinite graphs, equalities involving infinite cardinalities do not distinguish trees from many cyclic graphs. The definition by connectivity and absence of cycles, together with uniqueness of finite simple paths, remains applicable.
Local structure, distances, and centers
The degree of a vertex is the number of edges incident with it. A vertex of degree one is called a leaf, while vertices of larger degree are often called internal vertices. The unique vertex of a one-vertex tree has degree zero and is treated separately in degree-based statements. For a finite tree with vertices, counting each edge at both endpoints gives
Thus the average degree is , strictly less than two. Although a tree can have vertices of very high degree, those vertices must be balanced by leaves.
Every finite tree with at least two vertices has at least two leaves. One proof considers a longest simple path: either endpoint must be a leaf, since an additional neighbor outside the path would extend it, while an additional neighbor on the path would create a cycle. A more precise identity relates the number of leaves to vertices of degree at least three:
Vertices of degree two contribute nothing. Consequently, a tree whose maximum degree is at most two is a path, and a tree with a single vertex of degree is a star.
The distance between two vertices is the number of edges in their unique path. It defines a metric on the vertex set: distances are nonnegative and symmetric, vanish exactly when the vertices coincide, and satisfy the triangle inequality. Assigning a positive length to every edge produces a weighted tree metric by summing lengths along paths. Unlike an arbitrary shortest-path metric, a tree metric has a fixed route between each pair of points; changing an edge length changes route lengths but not the routes themselves.
The diameter is the largest distance between two vertices, and the eccentricity of a vertex is its greatest distance from any vertex. A center minimizes eccentricity. A finite tree has either one center or two adjacent centers, located at the midpoint or the two middle vertices of any longest path. Repeatedly removing all current leaves until only one vertex or one edge remains identifies this center. For an unweighted tree of diameter , the minimum eccentricity, called its radius, is .
A related but different notion is a centroid: a vertex whose deletion leaves no component containing more than half the original vertices. Every finite tree has one or two centroids; when there are two, they are adjacent. Centers minimize maximum distance, whereas centroids balance component sizes, so they need not coincide. Centroids are particularly important in recursive algorithms because their removal divides a tree into uniformly smaller pieces.
Rooted, ordered, and directed trees
A rooted tree is a tree with one distinguished vertex, its root. Rooting supplies a hierarchy without changing the underlying edges. Every nonroot vertex has a unique parent, namely the neighboring vertex on its path to the root. Its other neighbors are its children. The vertices encountered on the path from the root to a vertex are its ancestors, and vertices reached by moving repeatedly to children are its descendants. The descendants of a vertex, together with that vertex, form a rooted subtree.
The depth of a vertex is its distance from the root. The height of a finite rooted tree is the greatest depth, although some computing conventions count vertices rather than edges and therefore differ by one. An unrooted tree has no inherent upward direction, first generation, or ancestral order. Choosing a different root changes these relationships while preserving adjacency and distances. This distinction matters in applications: a diagram drawn with one vertex at the top need not represent a mathematically designated root.
A rooted tree is ordered, or a plane rooted tree, when the children of each vertex have a specified linear order. An unordered rooted tree records which vertices are children but not which child comes first. These structures have different notions of isomorphism and different counting formulas. For example, a root with two nonisomorphic child subtrees gives two ordered arrangements but only one unordered arrangement. The ordering is combinatorial; it does not depend on the precise coordinates used to draw the tree.
A binary tree usually means a rooted tree in which each vertex has at most two children, commonly distinguished as left and right. A full or proper binary tree has exactly two children at each internal vertex. A perfect binary tree is full and has all leaves at the same depth. A complete binary tree, in a common data-structure convention, has every level filled except possibly the last, which is filled from left to right. These terms are not universally standardized. In a finite full binary tree with internal vertices there are leaves and vertices altogether.
Orienting every edge away from the root gives an outward arborescence: the root has indegree zero, every other vertex has indegree one, and there is a directed path from the root to every vertex. Reversing all edges gives an inward arborescence. Both are special kinds of directed acyclic graph, but a general directed acyclic graph is not a tree: a vertex may have several parents, and the underlying undirected graph may contain cycles. Acyclicity in the directed sense alone is therefore insufficient to define a directed tree.
Enumeration and coding
Counting trees requires specifying what distinctions matter. In a labeled tree, vertices carry fixed, distinct labels, so different assignments of labels generally produce different objects. In an unlabeled tree, structures are identified when an adjacency-preserving bijection exists between their vertex sets. Rooting, ordering children, and imposing degree restrictions produce further counting problems. These choices account for the large differences between familiar tree-enumeration sequences.
The fundamental labeled enumeration is Cayley’s formula:
where is the number of trees on the fixed vertex set . Thus there are labeled trees on three vertices and on four vertices. Choosing a root in each labeled tree gives rooted labeled trees. Arthur Cayley published the formula in 1889, although equivalent counting results had appeared earlier in work by Carl Wilhelm Borchardt.
A particularly explicit proof uses the Prüfer sequence, introduced by Heinz Prüfer in 1918. Starting with a labeled tree, repeatedly remove the leaf with the smallest label and record its neighbor, stopping when two vertices remain. The result is a sequence of length , each entry drawn from the labels. Conversely, every such sequence reconstructs a unique tree: repeatedly join the smallest currently available label absent from the remaining sequence to the sequence’s first entry, then remove that entry. Finally join the last two available labels. This bijection proves Cayley’s formula.
The code also captures degree information. A vertex occurs in the Prüfer sequence exactly times. Consequently, for positive integers satisfying
the number of labeled trees with these prescribed degrees is
Uniformly sampling the entries of a Prüfer sequence therefore generates a uniformly random labeled tree. It does not generate a uniform distribution on unlabeled tree shapes, because different shapes admit different numbers of distinct labelings.
Ordered structures lead to other formulas. The number of full ordered binary trees with internal vertices is the Catalan number
These numbers also count rooted plane trees with edges, through a different structural correspondence. Generating functions encode such recursive constructions; for full ordered binary trees, the series , marking internal vertices, satisfies . By contrast, counting unlabeled unrooted trees requires accounting for symmetries. Richard Otter’s 1948 work established their asymptotic form , with approximately .
Spanning trees and minimal connectivity
A spanning tree of a connected graph is a subgraph that includes every vertex of and is itself a tree. Every finite connected graph has a spanning tree. One construction repeatedly removes an edge from a cycle; deleting such an edge preserves connectivity, and eventually no cycles remain. Another grows a connected set of vertices by adding an edge to a previously unreached vertex. These methods preserve all vertices while eliminating unnecessary connections.
A spanning tree provides a coordinate system for the cycles and separations of the original graph. Adding one non-tree edge to it creates a unique fundamental cycle, consisting of that edge and the tree path between its endpoints. Conversely, deleting a tree edge divides the vertices into two parts and determines a fundamental cut, formed by all edges of the original graph crossing between those parts. For a connected graph with vertices and edges, there are non-tree edges. The corresponding fundamental cycles form a basis of the cycle space when edge sets are added by symmetric difference.
If edges carry real weights, a minimum spanning tree minimizes the sum of its edge weights over all spanning trees. This is not the same problem as finding shortest paths from a source: minimizing the total installed network length need not minimize the distance from a particular vertex to every other vertex. Negative weights cause no conceptual difficulty for minimum spanning trees, since every candidate contains exactly edges and cycles are forbidden.
Two exchange principles support the standard algorithms. For any partition of the vertices into two nonempty sets, an edge of minimum weight crossing the partition belongs to some minimum spanning tree. If it is the unique lightest crossing edge, it belongs to every minimum spanning tree. Dually, an edge that is uniquely heaviest on a cycle belongs to no minimum spanning tree. These statements follow by adding an edge to a tree, identifying the resulting cycle, and exchanging one cycle edge for another while comparing weights.
Joseph Kruskal’s 1956 algorithm processes edges in nondecreasing weight order and retains an edge exactly when it joins two currently separate components. Prim’s algorithm grows one tree by repeatedly taking a lightest edge from the current tree to an outside vertex; closely related methods were described by Vojtěch Jarník in 1930 and Robert Prim in 1957. Otakar Borůvka developed an earlier minimum-spanning-tree algorithm in 1926 for electrical-network planning. Their correctness reflects the same cut and exchange structure, later generalized by the theory of matroids, in which forests are the independent sets of a graphic matroid.
Matrix methods and electrical interpretations
Trees have a close relationship with linear algebra. For a finite undirected graph, its adjacency matrix records which vertices are adjacent, and the diagonal degree matrix records their degrees. The graph Laplacian is
For a graph with positive edge weights, the weighted Laplacian instead uses weighted degrees and weighted adjacency entries. It is symmetric and positive semidefinite, and its null space consists of vectors that are constant on each connected component. In particular, a connected graph has a one-dimensional null space generated by the all-ones vector.
Kirchhoff’s matrix-tree theorem, established in 1847, states that the number of spanning trees of a finite graph equals any principal cofactor of its Laplacian: delete the same row and column, then take the determinant. In a weighted graph, this cofactor equals
where the sum ranges over spanning trees. Setting all weights equal to one recovers the ordinary count. A connected simple graph is itself a tree exactly when it has one spanning tree, so its Laplacian cofactors then equal one.
The theorem also has a spectral form. If a connected graph on vertices has Laplacian eigenvalues
then
For the complete graph, every nonzero Laplacian eigenvalue is , immediately yielding . For the complete bipartite graph with parts of sizes and , the theorem gives . Thus a matrix identity links structural connectivity, enumeration, and spectral information.
Another useful matrix is an oriented incidence matrix , obtained by assigning each edge an arbitrary direction and placing and at its initial and terminal vertices. In an unweighted graph, . The incidence columns of a forest are linearly independent; a cycle creates a signed dependence among columns. For a connected graph, choosing the columns belonging to a spanning tree selects a maximal independent set. This gives an algebraic explanation of the edge count and of the graphic-matroid interpretation.
Electrical networks make these identities concrete. Treating edge weights as conductances, the effective resistance between two vertices of a tree is the sum of the resistances along their unique path: no alternative route permits current to divide between competing paths. In a general weighted connected graph, if a spanning tree is sampled with probability proportional to the product of its edge conductances, the probability that an edge appears is . This identity connects random spanning trees with network response, rather than merely counting them.
Traversal, recognition, and recursive algorithms
The absence of cycles makes trees especially amenable to algorithmic processing. A finite graph can be tested for being a tree by checking connectivity and verifying that it has edges. Alternatively, a search can detect whether any edge leads to an already visited vertex other than the current vertex’s parent. With adjacency-list representation, these tests take time, where and are the numbers of vertices and edges; for a tree, . This use of asymptotic notation describes growth in computational cost rather than a particular machine’s running time.
Depth-first search follows a branch as far as possible before backtracking. Breadth-first search explores vertices by increasing distance from a starting vertex. In an arbitrary connected graph, both produce spanning trees, but they preserve different information: a breadth-first search tree records shortest unweighted distances from its root, whereas a depth-first search tree organizes recursive exploration and ancestor relationships. When the input is already a tree, either traversal visits every edge only a constant number of times.
Rooted trees support preorder and postorder computations. Preorder processes a vertex before its child subtrees; postorder processes those subtrees before the vertex. Subtree size, for example, obeys
Evaluating this recurrence in postorder computes all subtree sizes in linear time. Heights, leaf counts, and many expressions associated with hierarchical data follow similar recurrences. An explicit stack can replace recursive function calls when the tree’s height would otherwise create a deep call stack.
Dynamic programming on trees works because deleting an edge separates the problem into parts that interact through a small boundary. For a maximum-weight independent vertex set, let be the best weight in the subtree rooted at when is included, and the best weight when it is excluded. Then
where the sums run over the children of . A single postorder traversal evaluates both states. The analogous independent-set problem on unrestricted graphs is computationally much harder.
Several global properties are also computable efficiently. Two breadth-first searches find a diameter of an unweighted tree: start anywhere, find a farthest vertex, then search again from that vertex. Lowest-common-ancestor queries ask for the deepest shared ancestor of two vertices; preprocessing through ancestor tables or traversal-based range-minimum structures supports many subsequent queries efficiently. Tree isomorphism can be tested through canonical encodings of rooted branches, using the one or two centers to handle unrooted trees. For unordered trees, sorting child encodings removes dependence on an arbitrary drawing order.
Decomposition, separators, and treewidth
Deleting a vertex from a tree separates its neighboring branches, and deleting an edge separates the graph into exactly two components. This strong separation property explains much of the tractability of tree algorithms. Every nontrivial finite tree has small separators: a centroid is a one-vertex separator whose remaining components each contain at most half the vertices. Recursively selecting centroids produces a decomposition of logarithmic depth, useful for organizing distance queries and divide-and-conquer computations.
Trees also organize decompositions of graphs that contain cycles. A tree decomposition of a graph consists of a tree whose nodes carry sets of graph vertices, called bags. Every graph vertex must occur in at least one bag, every graph edge must have both endpoints together in some bag, and the bags containing any fixed graph vertex must form a connected subtree. The last requirement, often called the running-intersection condition, ensures that information about one vertex remains coherent across the decomposition.
The width of a tree decomposition is one less than its largest bag size. The treewidth of a graph is the minimum width among all its tree decompositions. A nonempty graph has treewidth at most one exactly when it is a forest; an edgeless nonempty graph has treewidth zero, while a forest containing an edge has treewidth one. Trees therefore provide the base case of a quantitative measure of how far a graph departs from tree-like structure. Long cycles have treewidth two, whereas large square grids have treewidth growing with their side length.
Many algorithms extend from trees to bounded-treewidth graphs by processing bags rather than single vertices. For a coloring or constraint-satisfaction problem, a state can record assignments on the vertices of the current bag. Adjacent bags exchange only the information needed on their intersection. The cost is typically exponential in the width but polynomial, often linear for fixed width and a suitable decomposition, in the graph’s size. Small treewidth can therefore make an otherwise difficult problem manageable without requiring the graph itself to be acyclic.
A related construction appears in probabilistic graphical models. When a distribution factors over a tree, messages passed along edges can compute marginal distributions exactly. Each message summarizes one side of an edge conditional on the boundary variable. More general models can sometimes be reorganized into a junction tree whose bags are clusters of variables. Exact inference then depends heavily on cluster size, paralleling the role of treewidth in combinatorial algorithms. The central structural fact is the same: overlapping local pieces must be arranged so that shared information stays connected.
Infinite trees and their boundaries
An infinite tree is an infinite connected graph with no finite cycle. Any two vertices are still joined by a unique finite simple path, but several familiar finite conclusions no longer hold. An infinite tree need not have leaves: the doubly infinite path has degree two everywhere, and an infinite -regular tree has degree at every vertex. It may also have no center of finite eccentricity. Consequently, arguments based on longest paths or finite degree sums cannot simply be transferred to the infinite setting.
A ray is a one-way infinite simple path. Kőnig’s infinity lemma states, in a standard tree formulation, that every infinite rooted tree in which each vertex has finitely many children contains a ray starting at the root. The finite-branching hypothesis is essential. A root with infinitely many leaf children gives an infinite tree of height one and contains no ray. The lemma underlies compactness arguments in combinatorics and logic: compatible finite choices can sometimes be extended into an infinite coherent sequence.
Infinite directions are formalized by ends. Two rays belong to the same end if, after deleting any finite set of vertices, tails of both rays lie in the same connected component. In a tree, two rays represent the same end precisely when they eventually share a common tail. A one-way infinite path has one end, a doubly infinite path has two, and an infinite regular tree of degree at least three has uncountably many. The ends of an infinite rooted binary tree correspond to infinite sequences of two choices and form a space naturally homeomorphic to the Cantor set.
Tree geometry also affects a random walk. The simple symmetric walk on the doubly infinite path is recurrent: it returns to its starting vertex with probability one. On the infinite -regular tree for , it is transient. Away from a chosen root, there is one neighboring vertex closer to the root and farther away. This outward branching yields a probability of ever reaching the root when starting at one of its neighbors. The contrast illustrates how volume growth can change long-term behavior even when every vertex has finite degree.
Trees also appear in group theory. The Cayley graph of a free group with respect to its free generators is a tree: a cycle would encode a nontrivial reduced word equal to the identity. Bass–Serre theory studies group actions on trees and relates them to decompositions of groups. Replacing graph edges by real intervals produces metric trees; more generally, an -tree is a metric space in which each pair of points is joined by a unique arc, isometric to a real interval.
Scientific and computational applications
A tree data structure stores linked records in a rooted hierarchy. Search trees organize keys, heaps support priority operations, and tries organize strings by shared prefixes. Their effectiveness depends on additional invariants, not merely on being trees. A balanced binary search tree keeps its height proportional to , so searches and updates require logarithmically many comparisons; an unbalanced tree can degenerate into a path and require linear time. A heap instead imposes an order between parents and children without globally sorting all keys. File systems are often presented as trees, although links and shared objects can make their actual reference structure a more general graph.
Syntax trees represent the compositional structure of expressions and programs. For the expression , a multiplication node can have an addition subtree and the leaf as its children. Evaluation proceeds from leaves toward the root, while transformations operate on subtrees. Parse trees retain grammatical derivation details; abstract syntax trees omit much of that surface structure. Trees also model decision procedures: internal nodes specify tests and leaves specify outcomes. In machine learning, a decision tree partitions an input space through successive tests, while collections of trees can combine many such partitions. The validity of these models depends on their construction and evaluation, not on the tree form alone.
In evolutionary biology, a phylogenetic tree represents hypothesized relationships among biological lineages or sequences. A rooted tree specifies a direction of ancestry, whereas an unrooted tree records branching relationships without identifying an ancestor. Edge lengths may represent elapsed time or expected evolutionary change, and these interpretations are not interchangeable. For labeled terminal taxa, the number of unrooted fully bifurcating tree topologies is ; the rooted counterpart is . The rapid growth of this search space is a central computational issue in phylogenetic inference. Processes such as hybridization and horizontal gene transfer can require networks rather than a single tree.
Communication and utility networks use trees when all sites must be connected without routing loops. A spanning tree can select an acyclic forwarding structure from a physically redundant network, while multicast trees organize delivery from a source to many recipients. Minimum spanning trees optimize total edge weight when the available vertices and edges are fixed. A Steiner tree problem differs by allowing additional junctions or, in its graph version, by requiring only a specified subset of terminals to be connected. These distinctions matter because superficially similar network diagrams can represent different optimization problems.
Trees also support data compression and branching-process models. A Huffman code assigns symbols to leaves of a binary tree, with root-to-leaf paths giving prefix-free binary codewords; symbol probabilities determine an optimal tree for minimizing expected codeword length among binary prefix codes. In a branching process, vertices represent individuals and child counts describe reproduction. For a Galton–Watson process with one initial individual and a nondegenerate offspring distribution, extinction occurs with probability one when the mean offspring number is at most one, whereas a mean greater than one gives a positive probability of indefinite survival. Here the tree is random, and its shape records an entire history of population growth.