# Definition:Rooted Tree

## 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 \set {r_T} \to T$ be the mapping defined by:

- $\map \pi t := \text {the node adjacent to $t$ on the path to $r_T$}$

Then $\map \pi t$ 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$.

### 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:

- $\set {s \in T: \map \pi s = t}$

where $\map \pi s$ denotes the parent mapping of $s$.

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

### 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.

### 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 \set {r_T}$ is in $\Gamma$
- $(3): \quad$ Each node in $\Gamma$ either:
- $\text {(a)}: \quad$ is a leaf node of $T$

- or:
- $\text {(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

- 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.