Rooted Trees 🌳

Have you ever used a folder system on a computer, a family tree, or a website menu? If so, you have already seen a rooted tree in action, students. Rooted trees are one of the most important ideas in discrete mathematics because they turn a tree into a structure with a clear starting point and direction. That makes it easier to describe relationships, organize data, and solve problems.

What is a rooted tree?

A tree is a connected graph with no cycles. A rooted tree is a tree in which one vertex is chosen as the root. This special vertex acts like the top or starting point of the tree. From the root, every other vertex can be reached by exactly one simple path.

In a rooted tree, the root gives the tree a natural direction. Instead of thinking of the graph as just a web of connections, we now think about how nodes are arranged in layers or levels below the root. This is useful in computing, biology, organization charts, and many other areas.

For example, imagine a company chart. The CEO may be placed at the top as the root. Managers are below the CEO, and employees are below the managers. The chart is organized by levels, and every person except the CEO has exactly one direct boss above them. That is the basic shape of a rooted tree 📌.

Main terminology

To work with rooted trees, students, you should know these terms:

Root: the chosen starting vertex.
Parent: the vertex directly above another vertex.
Child: a vertex directly below another vertex.
Siblings: vertices that share the same parent.
Ancestor: any vertex on the path from the root to a given vertex.
Descendant: any vertex below a given vertex.
Leaf: a vertex with no children.
Internal vertex: a vertex that is not a leaf.
Level: the distance from the root, often counted as the number of edges on the path from the root.
Height: the largest level of any vertex in the tree.

These words let us describe a rooted tree precisely instead of just drawing it.

How rooted trees are organized

A rooted tree creates a clear hierarchy. Every vertex except the root has exactly one parent. This is a key property. Because there are no cycles, there is only one path from the root to any vertex.

That means rooted trees are very good for representing decision processes or nested structures. For example, a file system on a computer starts with a main folder, and subfolders branch out from it. Each folder has one parent folder, and files or subfolders inside it are its children. The root folder is the starting point.

The level of a vertex tells us how far it is from the root. If the root is at level $0$, then its children are at level $1$, their children are at level $2$, and so on. In many textbooks, level numbering may start at $1$ instead, so always check the convention being used. The important idea is the same: vertices farther from the root are at deeper levels.

A rooted tree also gives a sense of order among the children of a vertex. In some applications, the children are treated as ordered from left to right. When that happens, the tree is called an ordered rooted tree. In other settings, the order does not matter.

Example: a simple rooted tree

Suppose the root $r$ has two children, $a$ and $b$. Vertex $a$ has children $c$ and $d$, while $b$ has one child $e$. The structure looks like this:

r \rightarrow \{a,b\}, \quad a \rightarrow \{c,d\}, \quad b \rightarrow \{e\}

Here:

$r$ is the root.
$a$ and $b$ are children of $r$.
$c$ and $d$ are children of $a$.
$e$ is a child of $b$.
$c$, $d$, and $e$ are leaves.
$a$ and $b$ are internal vertices.

Notice that every vertex except $r$ has exactly one parent. Also, there is exactly one path from $r$ to each vertex.

Important properties of rooted trees

Rooted trees still obey the main rules of trees, but the root adds extra structure. Here are some facts that help in problem solving:

A rooted tree with $n$ vertices has exactly $n-1$ edges, because every vertex except the root needs one edge to connect it to its parent.
There is exactly one path from the root to any vertex.
Every vertex except the root has one parent.
Leaves have no children.
The height of the tree is the maximum distance from the root to any leaf.

These properties are not just definitions. They can be used to prove results and solve counting problems.

Counting children and leaves

If a rooted tree has many vertices, it can be helpful to count them by level. For example, a tree with root $r$, three children at level $1$, and six leaves at level $2$ has $1 + 3 + 6 = 10$ vertices total.

If every internal vertex has exactly $k$ children, the tree is called a full $k$-ary rooted tree. A common special case is a binary tree, where each internal vertex has at most $2$ children. Binary trees are widely used in computer science for search, sorting, and expression parsing.

Rooted trees and paths, ancestors, and descendants

One of the strongest advantages of rooting a tree is that it makes family-like relationships clear. The root is the top ancestor of every vertex. For any vertex $v$, all vertices on the unique path from the root to $v$ are ancestors of $v$. Every vertex below $v$ in its subtree is a descendant of $v$.

A subtree of a rooted tree is formed by choosing a vertex and looking at that vertex together with all of its descendants. This is a very natural idea. For example, if the root of a website is the homepage, then a subtree could be the section of pages under “Sports” or “Science.” Each section branches into smaller sections and pages.

Example: ancestry in a rooted tree

Suppose $x$ is a child of $a$, and $a$ is a child of the root $r$. Then the path is

$r \to a \to x$

In this case:

$r$ and $a$ are ancestors of $x$.
$x$ is a descendant of $a$.
$x$ is a descendant of $r$.
$a$ is the parent of $x$.

This kind of reasoning is common in discrete mathematics because it lets us describe structures using simple, exact relationships.

How rooted trees fit into the bigger topic of trees

Rooted trees are a special form of trees. The broader topic of trees in graph theory includes any connected acyclic graph. Rooted trees add a chosen root, which gives direction and hierarchy.

This connection matters because many results about trees become easier to use once a root is selected. For example, algorithms often need a starting point. In spanning tree problems, a tree is selected from a graph. Then choosing a root can help with traversal methods like breadth-first search or depth-first search.

Rooted trees are also linked to recursion. A rooted tree can be defined in terms of smaller rooted trees attached to the children of the root. This makes them ideal for recursive proofs and recursive algorithms. In fact, many recursive structures in mathematics and computer science are modeled by rooted trees.

Real-world connections

Rooted trees appear in many places:

Family trees show ancestors and descendants.
Organization charts show managers and workers.
Folder systems show parent folders and subfolders.
Decision trees help with step-by-step choices.
Expression trees represent formulas in algebra and programming.

For instance, the expression $((2+3)\times 4)$ can be represented as a rooted tree where multiplication is the root operation and addition is a child operation. That structure helps computers evaluate expressions correctly.

Working with rooted trees in problem solving

When solving a rooted tree problem, students, it helps to follow a few steps:

Identify the root.
Find parent-child relationships.
Count levels and determine the height.
Locate leaves and internal vertices.
Check that there is exactly one simple path from the root to each vertex.

These steps help in proofs and in drawing or reading tree diagrams.

Example problem

A rooted tree has root $r$. The root has $3$ children. Each of those children has $2$ children. How many vertices are in the tree?

Solution:

Level $0$: $1$ vertex, the root $r$.
Level $1$: $3$ vertices.
Level $2$: $3 \times 2 = 6$ vertices.

So the total is

1 + 3 + 6 = 10

This example shows how rooted trees can be counted level by level.

Another useful fact is that rooted trees often support induction. If you want to prove something about every vertex in a rooted tree, you can prove it for the root and then show that if it is true for a vertex, it is true for its children. This “from parent to child” structure is one reason rooted trees are so powerful in discrete mathematics.

Conclusion

Rooted trees are trees with a chosen starting vertex called the root. This root creates direction, hierarchy, and clear relationships such as parent, child, ancestor, descendant, leaf, and level. Because of these ideas, rooted trees are easier to describe and use in counting, recursion, and real-world modeling. They are a central part of the broader study of trees in discrete mathematics and appear in many practical systems such as file directories, organization charts, and decision processes 🌟.

Study Notes

A rooted tree is a tree with one chosen vertex called the root.
Every vertex except the root has exactly one parent.
Vertices directly below a node are its children.
Vertices with the same parent are siblings.
A leaf has no children.
An internal vertex is not a leaf.
The level of a vertex is its distance from the root, using the chosen convention.
The height of a rooted tree is the greatest level of any vertex.
There is exactly one path from the root to every vertex.
Rooted trees are useful for representing hierarchies, recursion, and structured data.
Rooted trees are a special kind of tree and connect directly to the broader topic of trees in graph theory.