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

• Results about rooted trees can be found here.

## Sources

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