### Unit 8: Trees

Trees are a special case of graphs. Certain assumptions are made about the structure of trees, so various actions can be taken with them that would not work with graphs. Put simply, a tree is a nondirected graph where any two nodes are connected by exactly one path. There are no cycles in a tree. Although this definition is very simple, it has powerful consequences within graph theory and in the real world. In this unit, we will explore trees further.

**Completing this unit should take you approximately 4 hours.**

Upon successful completion of this unit, you should be able to:

- define the basic components of a tree;
- explain trees as a special case of graphs;
- discriminate between binary and nonbinary trees; and
- identify subgroups within a specific graph that includes all vertices and a minimum number of edges.

### 8.1: Introduction

Read this page. Take careful note of its definitions.

Getting a good grasp of the definition of a tree and of its components is essential to understanding and making good use of them.

Work these exercises to see how well you understand this material.

### 8.2: Spanning Trees

Read this page to get a basic overview of spanning trees.

A spanning tree T of an nondirected graph G is a subgraph that itself is a tree that includes all vertices of G, with a minimum possible number of edges. In general, a graph may have several spanning trees. This concept has a lot of implications regarding optimization of tree structure and traversal. Let us have a look at this idea.

Work these exercises to see how well you understand this material.

### 8.3: Rooted Trees

We can separate rooted trees from nondirected trees by noting that a rooted tree contains a special vertex, called the root. If we choose any other vertex in the tree, we know that there is a unique path from the root to that vertex. The implication is that there is a hierarchy of vertices. Lets us take a deep look at rooted trees.

Work these exercises to see how well you understand this material.

### 8.4: Binary Trees

Binary trees are special cases of rooted trees. Binary trees have zero or more nodes. Each node has at most two children. A node without children is called a leaf. This type of tree is the most commonly encountered in practice. That is why we spend additional time with them.

Work these exercises to see how well you understand this material.

### Unit 8 Assessment

- Receive a grade
Take this assessment to see how well you understood this unit.

- This assessment
**does not count towards your grade**. It is just for practice! - You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.

- This assessment