Rooted Tree — Definition, Formula & Examples

A rooted tree is a tree (a connected graph with no cycles) in which one specific vertex has been designated as the root, giving the tree a natural hierarchy of parent and child vertices.

A rooted tree is an ordered pair $(T, r)$ where $T = (V, E)$ is a connected acyclic graph and $r \in V$ is a distinguished vertex called the root. For every vertex $v \in V$ , there exists a unique path from $r$ to $v$ . The depth of $v$ is the length of this path, and the height of the tree is $\max_{v \in V} \text{depth}(v)$ .

How It Works

Choosing a root imposes a direction on every edge: away from the root toward the leaves. Each non-root vertex

v

has exactly one parent — the vertex adjacent to

v

on the unique path back to

r

. The children of

v

are all vertices whose parent is

v

. A vertex with no children is called a leaf. This parent-child structure turns an undirected tree into a hierarchy, which is why rooted trees appear everywhere from file systems to parse trees in compilers.

Worked Example

Problem: A tree

T

has vertex set

V = \{a, b, c, d, e\}

and edge set

E = \{\{a,b\}, \{a,c\}, \{b,d\}, \{b,e\}\}

. Root the tree at vertex

a

. Determine the parent, children, depth, and height information.

Step 1: Identify the root and its children. Vertex

a

is the root (depth 0). The vertices adjacent to

a

are

b

and

c

, so the children of

a

are

\{b, c\}

\text{depth}(a) = 0, \quad \text{children}(a) = \{b, c\}

Step 2: Move one level down. Vertices

b

and

c

both have depth 1. The parent of each is

a

. Vertex

b

is adjacent to

d

and

e

(besides its parent

a

), so

\text{children}(b) = \{d, e\}

. Vertex

c

has no neighbors other than

a

, so

c

is a leaf.

\text{depth}(b) = \text{depth}(c) = 1

Step 3: Vertices

d

and

e

each have parent

b

and depth 2. Neither has any other neighbors, so both are leaves. The height of the tree is the maximum depth.

\text{height}(T) = \max\{0,1,1,2,2\} = 2

Answer: The rooted tree has root

a

, internal vertices

\{a, b\}

, leaves

\{c, d, e\}

, and height 2.

Why It Matters

Rooted trees are the backbone of data structures in computer science — binary search trees, heaps, and tries are all rooted trees. In discrete mathematics courses, they appear in counting problems (Cayley's formula), recursive algorithms, and proofs by structural induction.

Common Mistakes

Mistake: Assuming a tree has a natural root. An unrooted tree is just a connected acyclic graph with no hierarchy; parent-child relationships only exist once you choose a root.

Correction: Always specify which vertex is the root before referring to parents, children, depth, or height. The same underlying tree can produce different rooted trees depending on the choice of root.