2.1 Definitions

Here is the formal definition of a tree. It is a little dry, confusing and boring, but in the end, this is what really counts!

We start with a set of nodes, let us use N to denote this. Then, we define a relation “parent of” in the form of P ⊆ N × N. A tree can, therefore, be represented by the tuple (N,P).

There is a number of restrictions on the relation P:

• We define a node called a “root” r ∈ N such that ∀(a,b) ∈ P : rb. This means that the root r is not the child of any other node. Furthermore, N must have at most one root. This means ∀a ∈ N − r : ∃(x,a) ∈ P.
• We need to enforce the following rule: ∀(a,b),(c,d) ∈ P : (b = d) ⇒ (a = c). This means that a node can only have one parent.
• The parental relation cannot be cyclic. To express this constraint, we define the predicate A (for ancestor). First of all, all parents are ancestors, which means ∀(a,b) ∈ P : A(a,b). Next, we define ancestry recursively: ∀a,b,c ∈ N : (A(a,b) ∧ A(b,c)) ⇒ A(a,c). In English, this means that “if a is an ancestor of b, and b is an ancestor of c, then a is an ancestor of c.”

A node n without a child is called a leave. In other words, if predicate L(n) states that n is a leave, then ∀n ∈ N : (∀(a,b) ∈ P : an) ⇔ L(n).

A tree without any nodes is called an empty tree.