A
tree is a connected graph that contains no simple circuits. Trees were first used to count certain
types of chemical compounds in 1857, by the English mathematician Arthur Cayley. Trees have
been used to solve problems in a wide range of disciplines since that time.
A tree is a connected undirected graph that does not contain any simple circuits. A tree cannot have
multiple edges or loops because it cannot have a simple circuit. As a result, any tree must be a simple
graph.
A tree is any connected graph that does not contain any simple circuits. What about graphs that don't
have any simple circuits that aren't always connected? These graphs are known as forests because
each of their connected components is a tree.
Figure 1. Example of a Forest
Rooted Tree
A specific vertex of a tree is designated as the root in many applications of trees. A rooted tree is one
with one vertex designated as the root and every edge pointing away from the root.
Figure 2. Rooted Tree
Example 1: In the rooted tree T (with root a) shown in Figure 3, find the parent of c, the children of g, the
siblings of h, all ancestors of e, all descendants of b, all internal vertices, and all leaves. What is the
subtree rooted at g?
Figure 3. Rooted Tree T
Page 1 of 8
Solution:
The parent of c is b. The children of g are h, i, and j. The siblings of h are i and j. The ancestors of e are
c, b, and a. The descendants of b are c, d, and e. The internal vertices are a, b, c, g, h, and j. The leaves
are d, e, f, i, k, l, and m. The subtree rooted at g
parent of c
children of g
siblings of h
all ancestors of e
all descendants of b
all internal vertices
all leaves
If a is a vertex in a tree, the subtree with a as its root is the tree's subgraph consisting of a and its
descendants, as well as all edges incident to these descendants. The Subtree Rooted at g at rooted tree
T is shown in figure 4.
Figure 4. Subtree Rooted at g
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.
Figure 5. Example of Rooted Tree
In the binary tree T shown in Figure 6, the left child of d is f and the right child is g. We show the left and
right subtrees of c in Figures 6(b) and 6(c), respectively.
Trees as Models
Page 2 of 8
Trees are used as models in a variety of fields, including computer science, chemistry, geology, botany,
and psychology.
Representing Organizations. A large organization's structure can be modeled using a tree with
roots. Each vertex in this tree represents an organizational position. An edge connecting two
vertices indicates that the person represented by the first vertex is the (direct) boss of the person
represented by the last vertices.
Computer File Systems. Directories can be used to organize files in computer memory. A directory
can contain files as well as subdirectories. The entire file system is stored in the root directory. A
file system can thus be represented as a rooted tree, with the root representing the root directory,
internal vertices representing subdirectories, and leaves representing ordinary files or empty
directories.
Binary Search Tree
One of the most important tasks in computer science is searching for items in a list. Our primary goal is
to implement a searching algorithm that efficiently finds items when they are completely ordered. This is
possible by employing a binary search tree, which is a binary tree in which each child of a vertex is
designated as a right or left child, no vertex has more than one right or left child, and each vertex is
labeled with a key, which is one of the items.
Example 1. Develop a binary search tree with the words mathematics, physics, geography, zoology,
meteorology, geology, psychology, and chemistry in it (using alphabetical order).
Solution:
Page 3 of 8
Figure 6. Constructing a Binary Search Tree
Tree Traversal
I
nformation is frequently kept in rooted trees that are organized. To access data, we require
processes for going to each vertex of an ordered rooted tree. We'll go through many crucial
techniques for traversing every vertex of an ordered rooted tree. Various expression types,
including arithmetic expressions containing numbers, variables, and operations, can also be
represented by ordered rooted trees. In order to evaluate these expressions, it can be helpful to look
at the various listings of the vertices of ordered rooted trees that were used to represent the
expressions.
Traversal Algorithms
1. Preorder Traversal. Visit root, visit subtrees from left to right
Page 4 of 8
2. Inorder Traversal. The inorder traversal begins by traversing T1 in inorder, then visiting r. It
continues by traversing T2 in inorder, then T3 in inorder,..., and finally Tn in inorder.
Page 5 of 8
3. Postorder Traversal. Visit subtress from left to right. Visit root.
Page 6 of 8
Page 7 of 8
LEARNING ACTIVITIES
1. Consider the following rooted tree
1. Which vertex is the root?
2. Which vertices are internal?
3. Which vertices are leaves?
4. Which vertices are children of j?
5. Which vertex is the parent of h?
6. Which vertices are siblings of o?
7. Which vertices are ancestors of m?
8. Which vertices are descendants of b?
9. Draw the subtree of the tree that is rooted at
a. a
b. c
c. e
10. In which order are the vertices of the ordered rooted tree visited using:
a. Preorder traversal
b. Inorder traversal
c. Postorder traversal
2. Build a binary search tree for the words banana, peach, apple, pear, coconut, mango, and papaya
using alphabetical order
Page 8 of 8