Lecture 11.
Introduction to Trees
Reading: Sections 1.9; Practice: Activity 11.19 in this lecture note
Trees
Definition 11.1. A tree is a connected undirected graph with no simple circuits.
Trees
Definition 11.1. A tree is a connected undirected graph with no simple circuits.
Because a tree cannot have a simple circuit, a tree cannot contain multiple edges or
loops. Therefore, any tree must be a simple graph.
Trees
Definition 11.1. A tree is a connected undirected graph with no simple circuits.
Because a tree cannot have a simple circuit, a tree cannot contain multiple edges or
loops. Therefore, any tree must be a simple graph.
Example 11.2. Which of these graphs are trees?
Trees
Definition 11.1. A tree is a connected undirected graph with no simple circuits.
Because a tree cannot have a simple circuit, a tree cannot contain multiple edges or
loops. Therefore, any tree must be a simple graph.
Example 11.2. Which of these graphs are trees?
Theorem 11.3. An undirected graph is a tree if and only if there is a unique simple
path between any two of its vertices.
Forests
Definition 11.4. A forest is a graph with no simple circuit but is not connected. Each
of the connected components in a forest is a tree.
Example 11.5. Which of these are trees? Any forest?
Rooted Trees
Definition 11.6. A rooted tree is a tree in which one vertex has been designated as
the root and every edge is directed away from the root.
An unrooted tree can be converted into different rooted trees when different vertices
are chosen as the root.
1
Terminology for Rooted Trees
If v is a vertex of a rooted tree other than the root, the parent of v is the unique
vertex u such that there is a directed edge from u to v .
1
Terminology for rooted trees is a mix of botany and genealogy (such as the family tree of the
Bernoulli family of mathematicians).
1
Terminology for Rooted Trees
If v is a vertex of a rooted tree other than the root, the parent of v is the unique
vertex u such that there is a directed edge from u to v .
When u is a parent of v , v is called a child of u. Vertices with the same parent are
called siblings.
1
Terminology for rooted trees is a mix of botany and genealogy (such as the family tree of the
Bernoulli family of mathematicians).
The ancestors of a vertex are the vertices in the path from the root to this vertex,
excluding the vertex itself and including the root.
The ancestors of a vertex are the vertices in the path from the root to this vertex,
excluding the vertex itself and including the root.
The descendants of a vertex v are those vertices that have v as an ancestor.
A vertex of a rooted tree with no children is called a leaf. Vertices that have children
are called internal vertices.
A vertex of a rooted tree with no children is called a leaf. Vertices that have children
are called internal vertices.
If a is a vertex in a tree, the subtree with a as its root is the subgraph of the tree
consisting of a and its descendants and all edges incident to these descendants.
Practice 11.7. In the rooted tree T (with root a):
1 Find the parent of c, the children of g , the siblings of h, the ancestors of e, and
the descendants of b.
2 Find all internal vertices and all leaves.
3 What is the subtree rooted at g ?
m-ary Rooted Trees
Definition 11.8. A rooted tree is called an m-ary tree if every internal vertex has no
more than m children. The tree is called a full m-ary tree if every internal vertex has
exactly m children. An m-ary tree with m = 2 is called a binary tree.
Example 11.9. Are the following rooted trees full m-ary trees for some positive
integer m?
Properties of Trees
Theorem 11.10. A tree with n vertices has n − 1 edges.
Properties of Trees
Theorem 11.10. A tree with n vertices has n − 1 edges.
Theorem 11.11. A full m-ary tree with i internal vertices has n = m × i + 1 vertices.
Properties of Trees
Theorem 11.10. A tree with n vertices has n − 1 edges.
Theorem 11.11. A full m-ary tree with i internal vertices has n = m × i + 1 vertices.
Theorem 11.12 Theorem 11.11 gives the following properties:
1 A full m-ary tree with n vertices has i = (n − 1)/m internal vertices and
ℓ = [(m − 1)n + 1]/m leaves,
2 A full m-ary tree with i internal vertices has n = mi + 1 vertices and
ℓ = (m − 1)i + 1 leaves,
3 A full m-ary tree with ℓ leaves has n = (mℓ − 1)/(m − 1) vertices and
i = (ℓ − 1)/(m − 1) internal vertices.
Properties of Trees
Theorem 11.10. A tree with n vertices has n − 1 edges.
Theorem 11.11. A full m-ary tree with i internal vertices has n = m × i + 1 vertices.
Theorem 11.12 Theorem 11.11 gives the following properties:
1 A full m-ary tree with n vertices has i = (n − 1)/m internal vertices and
ℓ = [(m − 1)n + 1]/m leaves,
2 A full m-ary tree with i internal vertices has n = mi + 1 vertices and
ℓ = (m − 1)i + 1 leaves,
3 A full m-ary tree with ℓ leaves has n = (mℓ − 1)/(m − 1) vertices and
i = (ℓ − 1)/(m − 1) internal vertices.
Example 11.13. How many edges and leaves does a full binary tree with 2000 internal
vertices have?
1 A full m-ary tree with n vertices has i = (n − 1)/m internal vertices and
ℓ = [(m − 1)n + 1]/m leaves,
2 A full m-ary tree with i internal vertices has n = mi + 1 vertices and
ℓ = (m − 1)i + 1 leaves,
3 A full m-ary tree with ℓ leaves has n = (mℓ − 1)/(m − 1) vertices and
i = (ℓ − 1)/(m − 1) internal vertices.
Practice 11.14. Suppose that someone starts a chain letter. Each person who
receives the letter is asked to send it on to four other people. Some people do this, but
others do not send any letters. How many people have seen the letter, including the
first person, if no one receives more than one letter and if the chain letter ends after
there have been 100 people who read it but did not send it out? How many people
sent out the letter?
Depth and Height
The depth d(v ) of a node v in a rooted tree is the number of edges in the path from
the root to v . The height of a rooted tree is the maximum value of d(v ) over all the
nodes in the tree. In other words, the height of a rooted tree is the length of the
longest path from the root to any vertex.
Depth and Height
The depth d(v ) of a node v in a rooted tree is the number of edges in the path from
the root to v . The height of a rooted tree is the maximum value of d(v ) over all the
nodes in the tree. In other words, the height of a rooted tree is the length of the
longest path from the root to any vertex.
Example 11.15. Find the depth of each
vertex in the rooted tree shown below.
What is the height of this tree?
Depth and Height
The depth d(v ) of a node v in a rooted tree is the number of edges in the path from
the root to v . The height of a rooted tree is the maximum value of d(v ) over all the
nodes in the tree. In other words, the height of a rooted tree is the length of the
longest path from the root to any vertex.
Example 11.15. Find the depth of each
vertex in the rooted tree shown below.
What is the height of this tree?
Theorem 11.16. There are at most mh leaves in an m-ary tree of height h; ℓ ≤ mh .
A rooted m-ary tree of height h is balanced if all leaves are at depths h or h − 1.
Example 11.17. Which of the rooted trees are balanced?
A rooted m-ary tree of height h is balanced if all leaves are at depths h or h − 1.
Example 11.17. Which of the rooted trees are balanced?
Corollary 11.18. If an m-ary tree of height h has ℓ leaves, then h ≥ ⌈logm ℓ⌉.
If the m-ary tree is full and balanced, then h = ⌈logm ℓ⌉.
(We are using the ceiling function here. Recall that ⌈x⌉ is the smallest integer greater than or
equal to x.)
Activity 11.19. A full m-ary tree T has 81 leaves and height 4.
(a) Give the upper and lower bounds for m.
(b) What is m if T is also balanced?