10.1 Tree Properties, Rooted Trees, and Binary Trees

Chapter 9 used branching diagrams to display conditional routes. Those diagrams had a special shape: branches separated but never rejoined to form a loop. We now study that shape as a mathematical object.

Trees appear in file systems, organization charts, search procedures, syntax, routing, compression, and decision making. To reason about all of these with one language, we begin with the smallest pieces.

Vertices and edges

A vertex is an individual object or location. The word node means the same thing in this chapter. We usually label vertices with symbols such as $a,b,c$.

An edge connects two different vertices. Because the connections in this section have no direction, the edge joining $a$ and $b$ can be written as the unordered pair

The order does not matter: $\{a,b\}=\{b,a\}$. Two vertices joined by an edge are adjacent, or neighbors.

The degree of a vertex $v$, written $\deg(v)$, is the number of edges touching it. For example, if $v$ is connected to three different neighbors, then $\deg(v)=3$.

Paths, connectedness, and cycles

A path from $v_0$ to $v_k$ is a sequence of distinct vertices

such that every consecutive pair is joined by an edge. Its length is the number of edges, which is $k$ in this notation.

A connection structure is connected when a path exists between every pair of vertices. Connectedness means no vertex is isolated from the rest of the structure.

A cycle is a closed route

whose intermediate vertices are distinct. A cycle returns to its starting vertex without immediately retracing an edge.

We can now define the central object.

> A tree is a connected, undirected structure with no cycles.

The one-vertex structure with no edges is also a tree: it is connected by convention and has no cycle.

Two first examples

A chain $a-b-c-d$ is a tree. Every vertex can reach every other, and no route closes into a loop.

A triangle with edges $\{a,b\},\{b,c\},\{c,a\}$ is not a tree because those three edges form a cycle. Three isolated vertices are also not a tree because they are disconnected.

An unrooted tree vertex of degree $1$ is called a leaf. A tree with at least two vertices always has at least two leaves. To see why, choose a path of greatest possible length. If either endpoint had another neighbor outside the path, we could extend the path; if that neighbor were already on the path, a cycle would exist. Therefore both distinct endpoints have degree $1$ and are leaves.

The unique-path property

In a tree, exactly one path joins any two vertices.

Why can there not be two? Suppose different paths connected vertices $u$ and $v$. Follow them from $u$ until they first separate, then continue until they meet again. The two different route segments would form a cycle. A tree has no cycle, so the second path cannot exist.

The converse also holds: if exactly one path joins every pair of vertices, then the structure is connected, and it cannot contain a cycle because a cycle would provide two routes between vertices on that cycle. Therefore it is a tree.

This gives an equivalent characterization:

Construct a connection network edge by edge. The workbench detects components and cycles in real time, highlights the unique route between selected vertices, and lets you repair a disconnected structure or remove one edge from a loop.

A tree with $n$ vertices has $n-1$ edges

Let $n$ be the number of vertices. Every finite tree satisfies

where $E$ is the set of edges and $|E|$ is its size.

We can justify the formula by induction, the proof method from Chapter 3.

1. A one-vertex tree has $0=1-1$ edges. 2. Assume every tree with $n$ vertices has $n-1$ edges. 3. Take a tree with $n+1$ vertices. Remove a leaf and the one edge touching it. The remaining structure is still a tree: removing an endpoint cannot create a cycle or separate any remaining pair. 4. By the induction hypothesis, the remaining tree has $n-1$ edges. Restoring the removed edge gives $n$ edges, which equals $(n+1)-1$.

The edge count alone is not enough. A structure with $n$ vertices and $n-1$ edges could contain a cycle in one component and an isolated vertex elsewhere. We need an additional condition. Either of the following is sufficient:

Each condition forces the missing half of the tree definition.

An edge whose removal disconnects a connected structure is called a bridge. Every edge of a tree is a bridge: if edge $\{u,v\}$ could be removed while $u$ and $v$ remained connected, the remaining path together with $\{u,v\}$ would have formed a cycle.

This makes trees minimally connected: removing any edge destroys connectedness. They are also maximally acyclic: adding an edge between two previously nonadjacent vertices creates exactly one cycle, using the old unique path plus the new edge.

Choosing a root creates a hierarchy

An unrooted tree describes symmetric connections. A rooted tree chooses one vertex as the root and views every other vertex relative to it.

Because a tree has a unique path from the root to any vertex $v$, the neighbor immediately before $v$ on that path is unambiguous. It is the parent of $v$, and $v$ is its child. The root has no parent. Every other vertex has exactly one parent.

Additional family terms follow from the same paths:

• vertices with the same parent are siblings;
• an ancestor of $v$ lies on the path from the root to $v$;
• a descendant of $v$ has $v$ on its root path;
• a leaf in a rooted tree has no children;
• an internal vertex has at least one child.

Changing the root does not change the vertices or edges, but it can change every parent, child, ancestor, and descendant relationship.

Depth and height

The depth of a vertex $v$ is the length of the unique path from the root to $v$:

The root has depth $0$. Vertices at the same depth form a level.

The height of a rooted tree is the greatest vertex depth:

Depth belongs to a vertex; height summarizes the whole rooted tree. A one-vertex rooted tree has height $0$.

Move the root through a fixed tree and watch every edge reorient into parent–child relationships. The lab recalculates levels, ancestors, descendants, leaves, and height, making clear which facts belong to the underlying tree and which depend on the chosen root.

Ordered and binary trees

In some rooted trees, the children of each vertex have a specified left-to-right order. Such a structure is an ordered rooted tree. The order matters even when the same vertices and parent–child edges remain.

A binary tree is an ordered rooted tree in which every vertex has at most two children, distinguished as the left child and right child. A vertex may have only a right child; left and right are positions, not merely counts.

Two special forms are useful:

• a full binary tree has either zero or two children at every vertex;
• a perfect binary tree is full and has every leaf at the same depth.

If a full binary tree has $I$ internal vertices and $L$ leaves, then

To see why, count edges in two ways. Every internal vertex contributes two child edges, so there are $2I$ edges. The tree has $I+L$ total vertices and therefore $I+L-1$ edges. Equating the counts gives

and hence $L=I+1$.

A perfect binary tree of height $h$ has $2^d$ vertices at depth $d$. Summing all levels gives

total vertices and $2^h$ leaves.

These formulas do not apply to every binary tree. A long binary chain can have one vertex per level. Always check “full” or “perfect” before using a specialized count.

Section checklist

• A tree is connected and acyclic.
• A tree has exactly one path between every pair of vertices.
• A finite tree with $n$ vertices has $n-1$ edges.
• Removing any tree edge disconnects it; adding one missing edge creates one cycle.
• Choosing a root creates parent, child, depth, and height relationships.
• Binary trees distinguish left and right child positions.
• Full and perfect are additional conditions, not synonyms for binary.

The structure is now defined. Section 10.2 asks how an algorithm can visit every vertex in a precise, reproducible order.