# Definition:Rooted Tree

## Contents

## Definition

A **rooted tree** is a tree with a countable number of nodes, in which a particular node is distinguished from the others and called the **root node**:

## Root Node

Let $T$ be a rooted tree.

The **root node** of $T$ is the node of $T$ which is distinguished from the others by being the ancestor node of every node of $T$.

## Parent

Let $T$ be a rooted tree whose root is $r_T$.

Let $t$ be a node of $T$.

From Path in Tree is Unique, there is only one path from $t$ to $r_T$.

Let $\pi: T \setminus \left\{{r_T}\right\} \to T$ be the mapping defined by:

- $\pi \left({t}\right) := \text{the node adjacent to $t$ on the path to $r_T$}$

Then $\pi \left({t}\right)$ is known as the **parent node** of $t$.

The mapping $\pi$ is called the **parent mapping**.

### Ancestor

Let $T$ be a rooted tree with root $r_T$.

Let $t$ be a node of $T$.

An **ancestor node** of $t$ is a node in the path from $t$ to $r_T$.

This path is indeed unique, by Path in Tree is Unique.

### Proper Ancestor

A **proper ancestor node** of $t$ is an ancestor node of $t$ that is not $t$ itself.

## Child Node

Let $T$ be a rooted tree with root $r_T$.

Let $t$ be a node of $T$.

The **child nodes** of $t$ are the elements of the set:

- $\left\{{s \in T: \pi \left({s}\right) = t}\right\}$

where $\pi \left({s}\right)$ denotes the parent mapping of $s$.

That is, the **children** of $t$ are all the nodes of $T$ of which $t$ is the parent.

### Grandchild Node

A child of a child node of a node $t$ can be referred to as a **grandchild node** of $t$.

In terms of the parent mapping $\pi$ of $T$, a **grandchild node** of $t$ is a node $s$ such that:

- $\pi \left({\pi \left({s}\right)}\right) = t$

### Descendant

Let $T$ be a rooted tree with root $r_T$.

Let $t$ be a node of $T$.

A **descendant node** $s$ of a $t$ is a node such that $t$
is in the path from $s$ to $r_T$.

That is, the **descendant nodes** of $t$ are all the nodes of $T$ of which $t$ is an ancestor node.

### Proper Descendant

A **proper descendant node** of $t$ is a descendant of $t$ which is not $t$ itself.

## Sibling

Let $T$ be a rooted tree with root $r_T$.

Two children of the same node of $T$ are called **siblings**.

That is, **siblings** are nodes which both have the same parent.

## Leaf Node

Let $v$ be a node of a tree $T$.

Then $v$ is a **leaf node** of a $T$ if and only if $v$ is of degree $1$.

If $T$ is a rooted tree, this is equivalent to saying that $v$ has no child nodes.

## Branch

Let $T$ be a rooted tree with root node $r_T$.

A subset $\Gamma$ of $T$ is a **branch** if and only if all the following conditions hold:

- $(1): \quad$ The root node $r_T$ belongs to $\Gamma$
- $(2): \quad$ The parent of each node in $\Gamma \setminus \left\{{r_T}\right\}$ is in $\Gamma$
- $(3): \quad$ Each node in $\Gamma$ either:
- $(a): \quad$ is a leaf node of $T$

- or:
- $(b): \quad$ has exactly one child node in $\Gamma$.

## Also known as

In some contexts, in which only a **rooted tree** would make sense, the term **tree** is often used.

## Also see

- Definition:Tree (Graph Theory)
- Results about
**rooted trees**can be found here.

## Sources

- 1996: H. Jerome Keisler and Joel Robbin:
*Mathematical Logic and Computability*... (previous) ... (next): $\S 1.7$: Tableaus

- For their purposes, they refer to this concept just as a
**tree**: they have no use for the unrooted version.