Back to course 'CS202: Discrete Structures'

Topic outline

  • Unit 8: Trees

    Collapse all Expand all

    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

      • page icon
        Quick Introduction to Trees Page
        Students must
        Mark as done

        Read this page. Take careful note of its definitions.

      • page icon
        Formal Introduction to Trees Page
        Students must
        Mark as done

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

      • book icon
        Try It Now Book
        Students must
        Mark as done

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

    • 8.2: Spanning Trees

      • page icon
        Overview of Spanning Trees Page
        Students must
        Mark as done

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

      • page icon
        Detailed Discussion of Spanning Trees Page
        Students must
        Mark as done

        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.

      • book icon
        Try It Now Book
        Students must
        Mark as done

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

    • 8.3: Rooted Trees

      • page icon
        Rooted Trees Page
        Students must
        Mark as done

        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.

      • book icon
        Try It Now Book
        Students must
        Mark as done

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

    • 8.4: Binary Trees

      • page icon
        Binary Trees Page
        Students must
        Mark as done

        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.

      • book icon
        Try It Now Book
        Students must
        Mark as done

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

    • Unit 8 Assessment

      • quiz icon
        Unit 8 Assessment Quiz
        Students must
        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.