Trees

Trees play an important role in logical systems. In this tutorial, I will introduce some terminology for reasoning about trees.

A tree is a tuple \((T, E)\), where \(T\) is a nonempty set, whose elements are called nodes, and \(E\) is a relation on \(T\), \(E\subseteq T\times T\), called the immediate edge relation, satisfying the following conditions: For all nodes, \(n, n', m\in T\),

Every node has a unique predecessor: If \(nEm\) and \(n' Em\), then \(n=n'\),
There are no cycles: If \((n_1,\ldots, n_k)\) is a sequence of nodes where for each \(i=1,\ldots, k-1\), \(n_iEn_{i+1}\), then \(n_1\ne n_k\), and
Between any two nodes there is a unique path: For each \(n, n'\in T\) there is a unique sequence \(n_1, n_2, \ldots, n_m\) such that \(n=n_1En_2\cdots En_m=n'\).

The following terminology will be used when talking about trees. Let \((T, E)\) be a tree.

For a node \(n\in T\), the successors or children of \(n\) are \(\{n'\ |\ nEn'\}\).
For a node \(n\in T\), the predecessor or parent of \(n\) is the set \(\{n'\ |\ n'En\}\). Note that this set contains either no elements or exactly one element.
A node \(n\in T\) is called the root of the tree when the set of predecessors of \(n\) is \(\varnothing\).
The arity of a node is the number of successors. The leaves of a tree are the nodes with no successors (i.e., the nodes with arity 0).
A path in \((T,E)\) is a sequence of nodes connected by an edge relation: that is, a path is a sequence \((n_1,n_2,\ldots, n_k)\) such that for each \(i=1,\ldots,k-1\), \(n_iEn_{i+1}\). The length of a path is equal to the number of edges along that path (equivalently, one minus the number of nodes).
The height of \((T,E)\) is the length of the longest path.

As an example, let \(T\) and \(E\) be defined as follows:

\[ T=\{n_1, n_2, n_3, n_4, n_5, n_6, n_7, n_8\} \]

\[ E=\{(n_1,n_2), (n_1,n_3), (n_3, n_4), (n_3, n_5), (n_3, n_6), (n_2, n_7), (n_6, n_8)\} \]

We can depict this tree as follows:

The root of the above tree is \(n_1\) The leaves are \(n_8, n_5, n_4,\) and \(n_7\).
The successors of \(n_3\) are \(\{n_6,n_5, n_4\}\) and the predecessor of \(n_3\) is \(\{n_1\}\).
An example of two paths in the tree are \((n_3,n_5)\) and \((n_1,n_3,n_6)\).
The height of the tree is 3: the longest path in the tree is \((n_1,n_3,n_6, n_8)\) which has length 3.

Warning

We defined the predecessor of a node as a set, but the set will consist of either no elements (if the node is a root) or a single element (since every node as at most one predecessor). So, we will often say, for instance, "the parent of \(n_3\) is \(n_1\)".

A labelling of a tree \((T,E)\) is a function \(f\) defined on the set of nodes deﬁned on the set of nodes \(T\). The labelling \(f\) is a right labelling when we write \(f(n)\) to the right of eacn node \(n\), and a left labelling when we write \(f(n)\) to the left of each noe \(n\). A labelled tree is a tree together with a labelling.

Exercises

A binary tree is a tree where every node has at most 2 children. Suppose that there are 6 nodes, i.e., \(T=\{1, 2, 3, 4, 5, 6\}\). What is the maximum height of a binary tree on \(T\)? What is the minimum height of a binary tree on \(T\)?
Show Answer
The maximum height of a binary tree with 6 nodes is 5:
```
    graph LR
    A((1)) --> B((2));
    B((2)) --> C((3));
    C((3)) --> D((4));
    D((4)) --> E((5));
    E((5)) --> F((6));
```
The minimum height of a binary tree with 6 nodes is 2:
```
    graph TD
    A((1)) --> B((2));
    A((1)) --> C((3));
    B((2)) --> D((4));
    B((2)) --> E((5));
    C((3)) --> F((6));
```
In general, the minimum height of a binary tree with \(n\) nodes is \(\lfloor\log_2(n)\rfloor\).
Consider the following tree:
```
    graph TD
    A((2)) --> B((1));
    A((2)) --> C((3));
    B((1)) --> D((4));
    C((3)) --> F((6));
    F((6)) --> E((5));
    F((6)) --> G((7));
```
- What is the height of the tree?
- Which node is the root of the tree?
- Which nodes are the leaves of the tree?
- Which nodes are all the children of node 6?
- Is the tree a binary tree?
- Which node is the predecessor of 3?
Show Answer
- The height of the tree is 3.
- The root of the tree is node 2.
- The leaves of the tree are \(\{4, 5, 7\}\).
- The children of node 6 are \(\{5, 7\}\).
- The tree is a binary tree (the arity of every node is either 0, 1 or 2)
- The predecessor of 3 is node 2.