Applications of Trees
Course Code: 00090 Course Title: Discrete Mathematics
Dept. of Computer Science
Faculty of Science and Technology
Lecturer No: 22 Week No: 12 Semester:
Lecturer: Name & email
Lecture Outline
9.2 Applications of Trees
• Binary Search Tree (BST)
Objectives and Outcomes
• Objectives: To understand various applications of trees, to
understand binary search tree (BST) and the algorithm for
constructing binary search tree.
• Outcomes: The students are expected to be able to
explain applications of trees; be able to construct a BST
from a given list of items.
Common Uses of Trees
Manipulate hierarchical data
Make information easy to search
Manipulate sorted lists of data
As a workflow for compositing digital images for
visual effects
Routing Algorithms
Applications of Trees
Three problems can be studied using trees –
1) How should items in a list be stored so that an item
can be easily located?
2) What series of decisions should be made to find an
object with a certain property in a collection of
objects of a certain type?
3) How should a set of characters be efficiently coded
by bit strings?
Applications of Trees
• Binary search tree
– A simple data structure for sorted lists
• Decision tree
– A rooted tree where each vertex represents a possible
outcome of a decision and the leaves represent the
possible solutions
– Minimum comparisons in sorting algorithms
• Prefix code
– A code that has the property that the code of a character is
never a prefix of the code of another character
– Huffman coding
Binary Search Tree (BST)
• A binary tree in which each child of a vertex is
designated as a right or left child.
• No two vertex has more than one right child or left
child, and each vertex is labeled with a key, which is
one of the items.
• Vertices are assigned keys so that the key of a vertex
is both larger than the keys of all vertices in its left
subtree and smaller than the keys of all vertices in its
right subtree.
Binary Search Trees (BST)
• Binary Search Tree (BST): A binary tree in
which the vertices are labeled with items so
that a label of a vertex is greater than the
labels of all vertices in the left subtree of this
vertex and is less than the labels of all vertices
in the right subtree of this vertex.
Binary Search Trees (BST): Example
• Items are stored at
individual tree nodes. 7
• We arrange for the tree to
always obey this invariant: 3 12
• For every item x,
• Every node in x’s left subtree
is less than x. 1 5 9 15
• Every node in x’s right
subtree is greater than x.
0 2 8 11
9
Is this a BST?
5
4 7
3 2 8 9
No, this is NOT a BST. Why?
Binary Search Trees (BST)
Binary search tree construction Algorithm
• Start with a tree containing just one vertex (the root).
• Let v = the root.
• To add a new item a, do the following until stop:
If a< v:
• If v has a left child, then v = left child of v(move to the left)
• Else add a new left child to v with this item as its key.
• Stop.
If a> v:
• If v has a right child, then v= right child of v(move to the right).
• Else add a new right child to v with this item as its key.
• Stop.
Construction of BST
• Example: Construct/Form a BST using the
numbers below.
5 9 8 1 2 4 6 10
Construction of BST
5 9 8 1 2 4 6 10
Class Work
• Construct/Form a BST using the numbers below.
13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18
Solution
Example 1
• EXAMPLE 1: Form a binary search tree for the words
mathematics, physics, geography, zoology,
meteorology, geology, psychology, and chemistry
(using alphabetical order).
Solution of Example 1
Solution: Figure 1 displays the steps used to construct this binary search tree.
The word mathematics is the key of the root. Because physics comes after
mathematics (in alphabetical order), add a right child of the root with key
physics. Because geography comes before mathematics, add a left child of the
root with key geography. Next, add a right child of the vertex with key physics,
and assign it the key zoology, because zoology comes after mathematics and
after physics. Similarly, add a left child of the vertex with key physics and
assign this new vertex the key meteorology. Add a right child of the vertex
with key geography and assign this new vertex the key geology. Add a left
child of the vertex with key zoology and assign it the key psychology. Add a
left child of the vertex with key geography and assign it the key chemistry.
(The reader should work through all the comparisons needed at each step.)
Solution of Example 1
Class work
• Exercise 1: Build a binary search tree for the words
banana, peach, apple, pear, coconut, mango, and
papaya using alphabetical order.
• Exercise 5: Using alphabetical order, construct a
binary search tree for the words in the sentence
“The quick brown fox jumps over the lazy dog.”
Books
• Rosen, K. H., & Krithivasan, K. (2012). Discrete
mathematics and its applications: with combinatorics and
graph theory. Tata McGraw-Hill Education. (7th Edition)
References
1. Discrete Mathematics, Richard Johnsonbaugh, Pearson education, Inc.
2. Discrete Mathematical Structures, Bernard Kolman, Robert C. Busby, Sharon Ross,
Prentice-Hall, Inc.
3. SCHAUM’S outlines Discrete Mathematics(2nd edition), by Seymour Lipschutz,
Marc Lipson
• University of Wisconsin-Madison
http://pages.cs.wisc.edu/~deppeler/cs367-common/readings/Trees/intro.html
• Bradfield School of Computer Science
https://bradfieldcs.com/algos/trees/introduction/
• Online tutorial https://www.javatpoint.com/discrete-mathematics-binary-search-
trees
• Istanbul Technical University https://web.itu.edu.tr/~gencata/courses/DM/trees.pdf
