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:

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

Infinite Tree

A rooted tree is infinite if it contains a countably infinite number of nodes.

Finite Tree

Similarly, a rooted tree is finite if it contains a finite number of nodes.

Parent

Consider a rooted tree $T$ whose root is $r_T$.

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

From Paths in Trees are Unique, there is only one path from $t$ to $r_T$.

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

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

Then $\pi \left({t}\right)$ is known as the parent (or parent node) of $t$, and $\pi$ as the parent function or parent mapping.

Root Node

The root node, or just root, is the one node in a rooted tree which, by definition, has no parent.

Ancestor

An ancestor (or ancestor node) of a node $t$ of a rooted tree $T$ whose root is $r_T$ is a node in the path from $t$ to $r_T$.

Thus, the root of a rooted tree $T$ is the ancestor of every node of $T$ (including itself).

Proper Ancestor

A proper ancestor of a node $t$ is an ancestor of $t$ which is not $t$ itself.

Children

The children (or child nodes) of a node $t$ in a rooted tree $T$ are the elements of the set:

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

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

The child of a child node of a node $t$ is a grandchild node of $t$.

Descendant

A descendant (or descendant node) $s$ of a node $t$ of a rooted tree $T$ whose root is $r_T$ is a node such that $t$ is in the path from $s$ to $r_T$.

That is, the descendants of $t$ are all the nodes of $T$ of which $t$ is an ancestor.

Proper Descendant

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

Sibling

Two children of the same node of a rooted tree are called siblings.

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

Leaf Node

A leaf node (or a terminal node, or just leaf) of a rooted tree $T$ is a node of $T$ which has no children.

Branch

A subset $\Gamma$ of a rooted tree $T$ is a branch iff:

• The root node $r_T$ belongs to $\Gamma$;
• The parent of each node in $\Gamma - \left\{{r_T}\right\}$ is in $\Gamma$;
• Each node in $\Gamma$ either:
  • Is a leaf node of $T$;
  • Has exactly one child in $\Gamma$.

Hence a node in $T$ with more than one child will be on more than one branch.

A leaf node will be on exactly one branch.

The length of a branch is defined as the number of ancestors of the leaf at the end of that branch.

Informally, then, a branch of a rooted tree is the path from the root to a leaf.

Note, however, that $\Gamma$ is infinite iff it has no leaf node at the end.

Sources

• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): $\S 1.7$

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