# Chapter 28. Rooted Trees

# Chapter 28. Rooted Trees

A rooted tree is a tree with one distinguished vertex called the root.

The root gives direction to an otherwise undirected structure. In an unrooted tree, no vertex has a privileged role. In a rooted tree, every vertex is understood by its position relative to the root. This turns a tree into a hierarchy.

Rooted trees are used to model ancestry, containment, dependency, syntax, search, decisions, and recursive computation.

## 28.1 Definition

Let

$$
T = (V,E)
$$

be a tree.

A rooted tree is a pair

$$
(T,r),
$$

where \(r \in V\) is a distinguished vertex called the root.

The underlying graph \(T\) remains an ordinary tree. The choice of root adds extra structure.

If \(v\) is any vertex of \(T\), then there is a unique simple path from \(r\) to \(v\). This path determines the position of \(v\) in the rooted tree.

## 28.2 Parent and Child

Let \(v\) be a vertex different from the root.

Since there is a unique path from the root \(r\) to \(v\), there is a unique vertex immediately before \(v\) on that path. This vertex is called the parent of \(v\).

If \(u\) is the parent of \(v\), then \(v\) is called a child of \(u\).

The root has no parent.

A vertex may have zero, one, or many children. A vertex with no children is called a leaf. A vertex with at least one child is called an internal vertex.

## 28.3 Ancestors and Descendants

Let \(u\) and \(v\) be vertices in a rooted tree.

The vertex \(u\) is an ancestor of \(v\) if \(u\) lies on the unique path from the root to \(v\).

The vertex \(v\) is then called a descendant of \(u\).

Every vertex is often counted as both an ancestor and a descendant of itself. When this convention is inconvenient, one uses the terms proper ancestor and proper descendant.

The root is an ancestor of every vertex. Every vertex is a descendant of the root.

## 28.4 Depth and Height

The depth of a vertex \(v\) is the length of the unique path from the root to \(v\).

Thus the root has depth

$$
0.
$$

If \(v\) has parent \(p\), then

$$
\operatorname{depth}(v) =
\operatorname{depth}(p)+1.
$$

The height of a rooted tree is the maximum depth of any vertex:

$$
\operatorname{height}(T) =
\max_{v \in V} \operatorname{depth}(v).
$$

A tree with one vertex has height \(0\).

The height measures how far the tree extends from its root.

## 28.5 Levels

The vertices at the same depth form a level.

The level \(i\) of a rooted tree is the set

$$
L_i = \{v \in V : \operatorname{depth}(v)=i\}.
$$

The root is the only vertex at level \(0\):

$$
L_0 = \{r\}.
$$

Levels provide a natural horizontal decomposition of the tree. They are especially useful in breadth-first search, shortest-path trees, and hierarchical data structures.

## 28.6 Subtrees

Let \(v\) be a vertex in a rooted tree.

The subtree rooted at \(v\) is the subgraph induced by \(v\) and all descendants of \(v\).

This subtree is itself a rooted tree with root \(v\).

Subtrees are the basic units of recursive reasoning. Many proofs and algorithms on rooted trees work by applying the same argument to each subtree.

If the children of \(v\) are

$$
c_1,c_2,\ldots,c_k,
$$

then the subtree rooted at \(v\) consists of \(v\) together with the subtrees rooted at those children.

## 28.7 Recursive Description

A rooted tree may be described recursively.

It consists of a root together with a finite collection of rooted subtrees attached to the root.

If the root has children

$$
c_1,c_2,\ldots,c_k,
$$

then each \(c_i\) is the root of a smaller rooted tree.

This gives the schematic form

$$
T =
r(T_1,T_2,\ldots,T_k),
$$

where \(T_i\) is the subtree rooted at \(c_i\).

If \(k=0\), then the tree consists only of the root, or the root is a leaf.

This recursive structure explains why rooted trees are central in algorithms and formal languages.

## 28.8 Ordered and Unordered Rooted Trees

A rooted tree may be ordered or unordered.

In an unordered rooted tree, the children of a vertex form a set. Their order has no meaning.

In an ordered rooted tree, the children of each vertex are arranged in a specified order, usually from left to right.

For example, if a vertex has children \(a\), \(b\), and \(c\), then the ordered list

$$
(a,b,c)
$$

differs from

$$
(b,a,c).
$$

Ordered rooted trees appear in syntax trees, expression trees, XML documents, JSON structures, and many parsing systems.

Unordered rooted trees appear in abstract hierarchy, taxonomy, and many mathematical counting problems.

## 28.9 Rooted Trees as Directed Graphs

A rooted tree can be converted into a directed graph by orienting every edge away from the root.

If \(u\) is the parent of \(v\), then the undirected edge

$$
\{u,v\}
$$

becomes the directed edge

$$
u \to v.
$$

The resulting directed graph has these properties:

| Property | Meaning |
|---|---|
| Root in-degree | The root has in-degree \(0\) |
| Non-root in-degree | Every other vertex has in-degree \(1\) |
| Acyclicity | There are no directed cycles |
| Reachability | Every vertex is reachable from the root |

Such a directed rooted tree is often called an arborescence.

One may also orient every edge toward the root. In that convention, every non-root vertex points to its parent.

## 28.10 Lowest Common Ancestor

Let \(u\) and \(v\) be two vertices in a rooted tree.

A common ancestor of \(u\) and \(v\) is a vertex that is an ancestor of both.

The lowest common ancestor, often written

$$
\operatorname{LCA}(u,v),
$$

is the common ancestor of \(u\) and \(v\) with greatest depth.

The lowest common ancestor is unique.

### Example

If two files lie in different subdirectories, their lowest common ancestor is the deepest directory containing both files.

The lowest common ancestor is important in algorithms, tree queries, phylogenetics, compilers, and network routing.

## 28.11 Paths in Rooted Trees

In an unrooted tree, every two vertices are joined by a unique simple path.

In a rooted tree, this path can be described using ancestors.

Let \(u\) and \(v\) be vertices, and let

$$
w = \operatorname{LCA}(u,v).
$$

Then the path from \(u\) to \(v\) goes upward from \(u\) to \(w\), then downward from \(w\) to \(v\).

Thus

$$
\operatorname{dist}(u,v) =
\operatorname{depth}(u)
+
\operatorname{depth}(v) -
2\operatorname{depth}(w).
$$

This formula is widely used in tree algorithms.

## 28.12 Rooted Tree Traversals

A traversal is a systematic procedure for visiting the vertices of a tree.

For rooted trees, common traversals include:

| Traversal | Rule |
|---|---|
| Preorder | Visit root, then subtrees |
| Postorder | Visit subtrees, then root |
| Level order | Visit vertices by increasing depth |

If the tree is ordered, the subtrees are visited according to the specified child order.

Preorder traversal is natural when a parent must be processed before its children.

Postorder traversal is natural when a parent depends on information computed from its children.

Level-order traversal is the same structure used by breadth-first search.

## 28.13 Size of a Rooted Tree

The size of a rooted tree is the number of vertices it contains.

The recursive formula for size is

$$
\operatorname{size}(T) =
1 + \sum_{i=1}^{k} \operatorname{size}(T_i),
$$

where \(T_1,T_2,\ldots,T_k\) are the subtrees rooted at the children of the root.

The term \(1\) counts the root.

This formula reflects the decomposition of the tree into root plus child subtrees.

## 28.14 Height Recursion

The height of a rooted tree can also be computed recursively.

If the root has no children, then

$$
\operatorname{height}(T)=0.
$$

If the root has child subtrees

$$
T_1,T_2,\ldots,T_k,
$$

then

$$
\operatorname{height}(T) =
1 + \max_{1 \leq i \leq k}\operatorname{height}(T_i).
$$

Thus a tree is tall when at least one of its subtrees is tall.

This recursion is used in the analysis of search trees, decision trees, and divide-and-conquer algorithms.

## 28.15 Branching Factor

The number of children of a vertex is its branching factor.

A rooted tree has maximum branching factor \(b\) if every vertex has at most \(b\) children.

If every internal vertex has exactly \(b\) children, the tree is called a full \(b\)-ary tree.

For example:

| Branching factor | Name |
|---|---|
| \(1\) | Path-like rooted tree |
| \(2\) | Binary tree |
| \(3\) | Ternary tree |
| \(b\) | \(b\)-ary tree |

Branching factor controls the growth of levels.

If a rooted tree has branching factor at most \(b\), then level \(i\) contains at most

$$
b^i
$$

vertices.

## 28.16 Counting Vertices by Height

Suppose a rooted tree has maximum branching factor \(b\) and height \(h\).

Then the number of vertices is at most

$$
1 + b + b^2 + \cdots + b^h.
$$

If \(b \neq 1\), this sum is

$$
\frac{b^{h+1}-1}{b-1}.
$$

If \(b=1\), the tree is a path and has at most

$$
h+1
$$

vertices.

These formulas are common in the analysis of search algorithms.

## 28.17 Applications

Rooted trees appear whenever structure has a distinguished origin or hierarchy.

| Application | Rooted tree interpretation |
|---|---|
| File system | Root directory and nested folders |
| Syntax tree | Grammar production hierarchy |
| Decision tree | Root question and branch outcomes |
| Search tree | Initial state and generated states |
| Organization chart | Top-level unit and subordinate units |
| Phylogenetic tree | Common ancestor and descendants |
| Web crawling | Seed page and discovered links |

The same mathematical structure supports many different interpretations.

## 28.18 Summary

A rooted tree is a tree with a distinguished vertex called the root.

The root induces parent-child relations, ancestors, descendants, depths, levels, and subtrees. These notions turn a tree into a hierarchical structure.

Rooted trees are naturally recursive. A rooted tree consists of a root and the rooted subtrees attached to its children.

This recursive and hierarchical structure makes rooted trees fundamental in algorithms, data structures, parsing, search, and dependency modeling.