Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section10.3Rooted Trees

In the next two sections, we will discuss rooted trees. Our primary foci will be on general rooted trees and on a special case, ordered binary trees.

Subsection10.3.1Definition and Terminology

A Rooted Tree
Figure10.3.1A Rooted Tree
List10.3.2Informal Definition and Terminology

What differentiates rooted trees from undirected trees is that a rooted tree contains a distinguished vertex, called the root. Consider the tree in Figure 10.3.1. Vertex \(A\) has been designated the root of the tree. If we choose any other vertex in the tree, such as \(M\), we know that there is a unique path from \(A\) to \(M\). The vertices on this path, \((A, D, K, M)\), are described in genealogical terms:

  • \(M\) is a child of \(K\) (so is \(L\))

  • \(K\) is \(M\)'s parent.

  • \(A\), \(D\), and \(K\) are \(M\)'s ancestors.

  • \(D\), \(K\), and \(M\) are descendants of \(A\).

These genealogical relationships are often easier to visualize if the tree is rewritten so that children are positioned below their parents, as in Figure 10.3.3.

With this format, it is easy to see that each vertex in the tree can be thought of as the root of a tree that contains, in addition to itself, all of its descendants. For example, \(D\) is the root of a tree that contains \(D\), \(K\), \(L\), and \(M\). Furthermore, \(K\) is the root of a tree that contains \(K\), \(L\), and \(M\). Finally, \(L\) and \(M\) are roots of trees that contain only themselves. From this observation, we can give a formal definition of a rooted tree.

A Rooted Tree, redrawn
Figure10.3.3A Rooted Tree, redrawn
Definition10.3.4Rooted Tree

  1. Basis: A tree with no vertices is a rooted tree (the empty tree).

  2. A single vertex with no children is a rooted tree.

  3. Recursion: Let \(T_1, T_2,\ldots,T_r\), \(r\geq 1\), be disjoint rooted trees with roots \(v_1\), \(v_2, \ldots \), \(v_r\), respectively, and let \(v_0\) be a vertex that does not belong to any of these trees. Then a rooted tree, rooted at \(v_0\), is obtained by making \(v_0\) the parent of the vertices \(v_1\), \(v_2, \ldots\), and \(v_r\). We call \(T_1, T_2, \ldots, T_r\), subtrees of the larger tree.

The level of a vertex of a rooted tree is the number of edges that separate the vertex from the root. The level of the root is zero. The depth of a tree is the maximum level of the vertices in the tree. The depth of a tree in Figure 10.3.3 is three, which is the level of the vertices \(L\) and \(M\). The vertices \(E\), \(F\), \(G\), \(H\), \(I\), \(J\), and \(K\) have level two. \(B\), \(C\), and \(D\) are at level one and \(A\) has level zero.

Example10.3.5A Decision Tree

Figure 2.1.2 is a rooted tree with Start as the root. It is an example of what is called a decision tree.

Example10.3.6Tree Structure of Data

One of the keys to working with large amounts of information is to organize it in a consistent, logical way. A data structure is a scheme for organizing data. A simple example of a data structure might be the information a college admissions department might keep on their applicants. Items might look something like this: \begin{equation*} \begin{split} ApplicantItem & = (FirstName,MiddleInitial,LastName,StreetAddress,\\ & City,State,Zip,HomePhone,CellPhone,EmailAddress,\\ & HighSchool,Major,ApplicationPaid,MathSAT,VerbalSAT,\\ & Recommendation1,Recommendation2,Recommendation3) \end{split} \end{equation*} This structure is called a “flat file”.

A spreadsheet can be used to arrange data in this way. Although a “flat file” structure is often adequate, there are advantages to clustering some the information. For example the applicant information might be broken into four parts: name, contact information, high school, and application data: \begin{equation*} \begin{split} ApplicantItem & = ((FirstName,MiddleInitial, LastName),\\ &((StreetAddress,City,State,Zip),\\ & (HomePhone,CellPhone),EmailAddress),\\ &HighSchool,\\ &(Major,ApplicationPaid,(MathSAT,VerbalSAT),\\ &(Recommendation1,Recommendation2,Recommendation3)) \end{split} \end{equation*} The first item in each ApplicantItem is a list \((FirstName, MiddleInitial, LastName)\), with each item in that list being a single field of the original flat file. The third item is simply the single high school item from the flat file. The application data is a list and one of its items, is itself a list with the recommendation data for each recommendation the applicant has.

The organization of this data can be visualized with a rooted tree such as the one in Figure 10.3.7.

Applicant Data in a Rooted Tree
Figure10.3.7Applicant Data in a Rooted Tree

In general, you can represent a data item, \(T\), as a rooted tree with \(T\) as the root and a subtree for each field. Those fields that are more than just one item are roots of further subtrees, while individual items have no further children in the tree.

Subsection10.3.2Kruskal's Algorithm

An alternate algorithm for constructing a minimal spanning tree uses a forest of rooted trees. First we will describe the algorithm in its simplest terms. Afterward, we will describe how rooted trees are used to implement the algorithm. Finally, we will describe a simple data structure and operations that make the algorithm quite easy to program. In all versions of this algorithm, assume that \(G = (V, E, w)\) is a weighted undirected graph with \(\lvert V\rvert = m\) and \(\lvert E\rvert = n\).

Step 1 can be accomplished using one of any number of standard sorting routines. Using the most efficient sorting routine, the time required to perform this step is proportional to \(n \log n\). The second step of the algorithm, also of \(n \log n\) time complexity, is the one that uses a forest of rooted trees to test for whether an edge should be added to the spanning set.

Note10.3.10

  1. Since we start the Kruskal's algorithm with \(m\) trees and each addition of an edge decreases the number of trees by one, we end the algorithm with one rooted tree, provided a spanning tree exists.

  2. The rooted tree that we develop in the algorithm is not the spanning tree itself.

Subsection10.3.3Sage Note - Implementation of Kruskal's Algorithm

Kruskal{'}s algorithm has been implemented in Sage. We illustrate how the spanning tree for a weighted graph in can be generated. First, we create such a graph

We will create a graph using a list of triples of the form \((\text{vertex},\text{vertex}, \text{label})\). The \(weighted\) method tells Sage to consider the labels as weights.

Next, we load the kruskal function and use it to generate the list of edges in a spanning tree of \(G\).

To see the resulting tree with the same embedding as \(G\), we generate a graph from the spanning tree edges. Next, we set the positions of the vertices to be the same as in the graph. Finally, we plot the tree.

Subsection10.3.4Exercises for Section 10.3

1

Suppose that an undirected tree has diameter \(d\) and that you would like to select a vertex of the tree as a root so that the resulting rooted tree has the smallest depth possible. How would such a root be selected and what would be the depth of the tree (in terms of \(d\))?

Answer
2

Use Kruskal's algorithm to find a minimal spanning tree for the following graphs. In addition to the spanning tree, find the final rooted tree in the algorithm. When you merge two trees in the algorithm, make the root with the lower number the root of the new tree.

Figure for exercise 10-3-2a
Figure for exercise 10-3-2b
3

Suppose that information on buildings is arranged in records with five fields: the name of the building, its location, its owner, its height, and its floor space. The location and owner fields are records that include all of the information that you would expect, such as street, city, and state, together with the owner's name (first, middle, last) in the owner field. Draw a rooted tree to describe this type of record

Answer
4

Step through Kruskel's Algorthm by hand to verify that the example of a minimal spanning tree using Sage in Subsection 10.3.3 is correct.