MPCS 50103 — Lecture 15

Trees

Trees are another special kind of graph with various interesting properties. This makes them interesting from a mathematical point of view (i.e. for studying) and these properties lend themselves to "useful" representations of data (i.e. for use in applications).

Typically, we think of trees when they're organized with the root at the top and growing downwards (apparently trees grow upside-down) as in family trees or organizational charts. However, the following definition gives us something more concrete to work with and we'll see that some results we've proven about cycles will come into play.

A graph $G$ is a tree if $G$ is connected and contains no cycles. A graph $G$ with no cycles is a forest.

The following are examples of trees.

A graph $G$ is a tree if and only if there is a unique path between any two vertices in $G$.

Suppose $G$ is a tree. Then $G$ is connected and has no cycles. Consider a pair of vertices $u, v$. Since $G$ is connected, there is a path between $u$ and $v$. Since $G$ contains no cycles, this path must be unique. Otherwise, if there were a second path, we can form a cycle.

Now suppose that every pair of of vertices $u$ and $v$ in $G$ has a unique path between them. Then $G$ is connected. Now, suppose for contradiction that $G$ contains a cycle and $u$ and $v$ are part of this cycle. The cycle exhibits two paths between $u$ and $v$, contradicting our assumption that there is a unique path between $u$ and $v$. Thus, $G$ does not contain any cycles. Therefore, $G$ is a tree.

One of the consequences of trees being cycle-less is that removing any single edge will disconnect the graph. In other words, a tree is about as barebones of a graph you can get that's stll connected. We can apply this idea to the notion of connectivity in graphs. We can think of this as finding a minimal connected subgraph of the graph such that every vertex is connected. One can see how this might be useful in something like road network where you're trying to figure out what the most important roads to clear after a snowfall are.

A spanning subgraph which is also a tree is called a spanning tree.

Here is a graph, with one possible spanning tree highlighted.

A graph $G$ is connected if and only if it has a spanning tree.

Suppose $G$ has a spanning tree $T$. Then there exists a path between every pair of vertices in $T$ and therefore, there exists a path between every pair of vertices in $G$. Then by definition, $G$ is connected.

Now, suppose $G$ is connected. Consider the connected spanning subgraph $H$ of $G$ with the minimal number of edges. Suppose $H$ contains a cycle. Then we can remove an edge from this cycle, since no edge in a cycle is a bridge. Therefore, $H$ contains no cycles and since $H$ is connected, it is a tree.

This result provides another way to determine the connectivity of a graph. But how do we build a spanning tree? This is actually quite simple: we just have to "explore" the graph. There are two approaches to doing this. In both, we first choose an arbitrary vertex to begin.

The first approach is to build a path from our starting vertex, as long as we can. Once we are unable to do so, we backtrack up the path we've just built to try to extend it to any vertices we haven't visited yet. This is called a depth-first traversal.

The example above was created via a depth-first traversal. Here is the same tree with the order of traversal labelled.

The second approach is to build paths by sweeping out from our source vertex, adding edges to all of its neighbours. Then for each of its neighbours, we repeat the process, as long as the vertices have not already been visited from a prior node. This is called a breadth-first traversal.

Here is the same graph, but with a spanning tree constructed from a breadth-first traversal, starting at the same vertex.

We can make these algorithms slightly more concrete. First, consider depth-first search.

For a graph $G = (V,E)$, create a subgraph $T$ of $G$ that contains an arbitrary vertex $v \in V$ and a list $L$ containing $v$.
For each vertex in $u \in L$, starting with the last vertex added,
1. Consider the neighbours of $u$. For each $x \in N(u)$, if $x$ is not already in $T$, add $x$ to $L$.
2. Let $x_0$ be the last vertex just added to $L$. Add $x_0$ and $(u,x_0)$ to $T$.

Then we can describe breadth-first traversal.

For a graph $G = (V,E)$, create a subgraph $T$ of $G$ that contains an arbitrary vertex $v \in V$ and a list $L$ containing $v$.
For each vertex in $u \in L$, starting with the first vertex added,
1. Consider the neighbours of $u$. For each $x \in N(u)$, if $x$ is not already in $T$ or $L$, add $x$ and $(u,x)$ to $T$. Then add $x$ to $L$.

Both of these algorithms construct a spanning tree for a given connected component. At the end of the process, we can check whether all vertices of $G$ are in the resultant tree $T$ to see if our graph is connected.

We note that both algorithms examine each edge of the graph once. This is much more efficient than using matrix multiplication with the adjacency matrix.

Binary trees

Very often, in computer science, we are concerned with binary trees as fundamental structures. These trees have a specific form which gives rise to even more special properties.

A rooted tree is a tree in which one vertex has been designated as the root. Let $T = (V,E)$ be a rooted tree and let $r$ be the root of $T$.

If $v \in V$ and $v \neq r$, then the parent of $v$ is its unique neighbour $u$ which is closer to $r$. The other neighbours of $v$ are its children. If $u$ and $v$ have the same parent, then they are siblings
An ancestor of $v$ is a vertex on the path between $r$ and $v$. A descendant of $v$ is a vertex $u$ such that $v$ is on the path between $r$ and $u$.
A leaf is a vertex with no children. If a vertex has children, it is an internal node.
Let $v$ be a vertex of $T$. The subtree with $v$ as its root is the subgraph of $T$ consisting of $v$ and its descendants and all incident edges.
A rooted tree is an $n$-ary tree if every internal vertex has at most $n$ children. An $n$-ary tree is full if every internal node has exactly $n$ children. A 2-ary tree is called a binary tree.
The height of a rooted tree is the number of vertices on the longest path between $r$ and a leaf.

Here is a ternary or 3-ary tree. It is not a full tree. The root of the tree is highlighted in red. The leaves are highlighted in green. The yellow vertex is the parent of the cyan vertex, and the cyan vertex is its child. The magenta vertex is an ancestor of the yellow and cyan nodes, and they are its descendants. The subtree rooted at the magenta vertex is the subgraph induced by it and its descendants.

For simiplicity, we will restrict our attention to binary trees. However, many of these results can generalize quite easily to $n \gt 2$. The notion of a subtree is quite useful for proving properties of rooted trees by induction.

Let $G = (V,E)$ be a binary tree with height $h \in \mathbb N$. Then $|V| \leq 2^h - 1$.

We will prove this by strong induction on $h$, the height of the binary tree.

Base case. We have $h = 1$. In this case, the binary tree of height 1 consists only of a root. Then we have $|V| = 1 \leq 2^h - 1$.

Inductive case. Let $k \in \mathbb N$ and suppose all binary trees of height $j \leq k$ have at most $2^j - 1$ vertices. Consider a binary tree $G = (V,E)$ with height $k+1$.

Let $r$ be the root of $G$. Consider the subtrees rooted at the children of $r$, say $T_1 = (V_1,E_1)$ and $T_2 = (V_2,E_2)$. Both $T_1$ and $T_2$ have height at most $k$. Then by our inductive hypothesis, $|V_1| \leq 2^k - 1$ and $|V_2| \leq 2^k - 1$. Then we get \begin{align*} |V| &= |V_1| + |V_2| + 1 \\ &= (2^k - 1) + (2^k - 1) + 1 \\ &= 2 \cdot (2^k - 1) + 1 \\ &= 2^{k+1} - 2 + 1 \\ &= 2^{k+1} - 1 \end{align*}

However, this suggests something quite interesting: why not define the notion of a binary tree inductively? Here is the standard computer science definition for a binary tree.

A binary tree is

empty, or
a node containing a value and two binary trees, called its left and right subtrees.

There are some notable differences with the graph theoretic notion. For one thing, trees are allowed to be empty. Also implicit in this definition is the idea of the binary tree as a data structure that is meant to store things. In this view, the node is an object that holds a value and links to the subtrees.

Just as we saw at the beginning of the quarter, these kinds of definitions translate quite nicely to programs. Well, almost. It is less nice in an imperative language like Python, so I'll demonstrate using Racket.

(define-type BinaryTree (U 'Empty Node))

(define-struct Node
  ([value : Integer]
   [left-sub : BinaryTree]
   [right-sub : BinaryTree]))

Notice how the definition maps on to the definition of the type. In the first line, we have that the BinaryTree is a union of either the symbol 'Empty or a structure Node. And what is a Node? It's a structure that contains a value, of type Integer, a left subtree, and a right subtree.

Let's see how this is useful by proving something. If we reinterpret the height of a binary tree to mean "nodes" rather than "vertices", we get the following.

Let $T$ be a binary tree and let $h(T)$ denote the height of $T$. Then

$h(T) = 0$ if $T$ is empty, and
$h(T) = 1 + \max\{h(T_L),h(T_R)\}$, where $T_L$ and $T_R$ are the left and right subtrees of $T$, respectively.

We will prove this by induction on $T$.

Base case. Since $T$ is empty, it has no root or leaf node, so it has height 0.

Inductive case. Assume that $h(T_L)$ and $h(T_R)$ are the number of nodes on the longest path between the root node and a leaf node for each tree, respectively. Consider $h(T)$. From whichever tree has greater height, we can construct a path by joining the root node of $T$ to the root of the corresponding subtree. This adds one to the height, giving us $1+\max\{h(T_L),h(T_R)\}$.

Notice that the above proof "works" even when the subtrees are empty. This proof gives us the following algorithm.

(: tree-height (-> BinaryTree Integer))
(define (tree-height t)
  (match t
    ['Empty 0]
    [(BinaryTree _ left right) 
     (+ 1 (max (tree-height left) (tree-height right)))]))

Here, we have defined a function tree-height which takes a BinaryTree and produces an Integer. Then t is matched (a fancy functional programming idiom): since it's a BinaryTree, it's either 'Empty or a Node. If it's 'Empty, then it has height 0.

If t is a Node, then it's a structure consisting of a value, a left subtree, and right subtree, in that order according to our definition. We can ignore the value since it's not used and we retrieve and locally name the left subtree left and the right subtree right. We recursively call tree-height on left and right, take the maximum, and add 1 and return the result.