Leaf (Tree) — Definition, Formula & Examples

A leaf (also called a pendant vertex) is a vertex in a tree that has exactly one edge connected to it. It sits at the 'end' of a branch with no further neighbors beyond its single connection.

In a tree $T = (V, E)$ , a vertex $v \in V$ is called a leaf if $\deg(v) = 1$ , meaning $v$ is incident to exactly one edge. Every finite tree with at least two vertices has at least two leaves.

Worked Example

Problem: A tree T has 7 vertices with the following adjacency: vertex A connects to B and C; vertex B connects to A, D, and E; vertex C connects to A and F; vertex F connects to C and G. Identify all leaves of T.

Step 1: Compute the degree of each vertex by counting its edges.

\deg(A)=2,\; \deg(B)=3,\; \deg(C)=2,\; \deg(D)=1,\; \deg(E)=1,\; \deg(F)=2,\; \deg(G)=1

Step 2: Select all vertices with degree exactly 1.

\text{Leaves} = \{D, E, G\}

Answer: The leaves of T are D, E, and G.

Why It Matters

Leaves play a central role in algorithms on trees. Repeatedly removing leaves ("pruning") is the basis of the algorithm to find the center of a tree and to compute Prüfer sequences, which encode labeled trees as integer sequences. In data structures like binary search trees and tries, leaf nodes are where queries terminate.

Common Mistakes

Mistake: Calling the root of a tree a leaf when it has degree 1.

Correction: In an unrooted tree, the root is not distinguished, so any degree-1 vertex is a leaf. In a rooted tree, a common convention is that the root is not considered a leaf even if it has degree 1 (e.g., a single-edge tree). Check which convention your course uses.