• 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

    • 8.2: Spanning Trees

      • Overview of Spanning Trees Page

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

      • Detailed Discussion of Spanning Trees Page

        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.

      • Try It Now Book

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

    • 8.3: Rooted Trees

      • Rooted Trees Page

        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.

      • Try It Now Book

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

    • 8.4: Binary Trees

      • Binary Trees Page

        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.

      • Try It Now Book

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

    • Unit 8 Assessment

      • Unit 8 Assessment Quiz
        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.