Week 7: Trees
Section………………………………………………………………………………………………. Page
Section 1: Definition and Elementary Results….....……………………………………………….…2
Section 2: Binary Trees……………….………………………………………………………….…...4
Section 2.1: Complete and Extended Binary Trees…………………………......................................5
Section 2.2: Representing Binary Trees in Memory…………………………….................................6
Section 3: Traversing Binary Trees………….....……………………………………………………..9
Section 4: Binary Search Tree……………………..............................................................................10
Section 4.1: Algorithm for Searching and Inserting in Binary Search Trees ………………………..10
Section 4.2: Algorithm for Deleting in a Binary Search Tree ……………………………………….12
Bibliography …………………………………………………………………………………………13
UU-MTH- 1005 Discrete Mathematics Page 1
Section 1: Definition and Elementary Results
Before defining a tree, let us first look at the definition of a connected graph and a cyclic graph.
A Connected Graph
As already defined before in week 7 lesson, part A, this is a type of a graph where there exists a path
between every pair of vertices. Example,
A Cyclic Graph
This is a graph with at least one cycle. For example,
The above graph is cyclic with two cycles namely 𝑎 − 𝑏 − 𝑐 − 𝑑 − 𝑎 and 𝑐 − 𝑓 − 𝑔 − 𝑒 − 𝑐.
Opposite to the cyclic graph is an acyclic graph; definitely, it is a graph with no cycles at all. Example,
UU-MTH- 1005 Discrete Mathematics Page 2
A Tree
A tree is, therefore, a connected graph with no cycles where the edges and the vertices are called
branches and nodes respectively, and the nodes without child nodes are called leaf nodes. If the tree
has a starting node, it is called a root.
Any tree having 𝑛 number of vertices will have 𝑛 − 1 number of edges.
Examples (Three different trees)
Ordered Rooted Tree
Before defining an ordered rooted tree, let us define the terms rooted tree, parent, child and internal
nodes.
A Rooted Tree
UU-MTH- 1005 Discrete Mathematics Page 3
This is a tree in which one node has been designated as the root (as a starting node) and every branch
(edge) is directed away from the root.
Parent
Let us suppose 𝑇 is a rooted tree; if 𝑣 is a node (which is not a root) in 𝑇, then the parent of 𝑣 is the
unique node 𝑢 such that there is a directed branch (edge) from 𝑢 to 𝑣.
Child
If 𝑢 is the parent of 𝑣, then 𝑣 is a child of 𝑢.
Internal Nodes
These are nodes that have children
An ordered rooted tree is therefore a rooted tree where the children of each internal node are ordered.
Example:
Section 2: Binary Trees
A binary tree is a rooted tree in which every internal node has a maximum of two children (or the
number of children is less than or equal to two).
UU-MTH- 1005 Discrete Mathematics Page 4
Example
Section 2.1: Complete and Extended Binary Trees
Complete Binary Tree
This is a binary tree whose all levels, except with the possibility of the last ones, have the maximum
number of possible nodes as left as possible.
Example
UU-MTH- 1005 Discrete Mathematics Page 5
Extended Binary Tree
This is a type of binary tree which displays the result of a complete binary tree by replacing every
missing child with a leaf node.
Example
Section 2.2: Representing Binary Trees in Memory
There are two different methods on how to represent a binary tree in computer memory. These methods
are array representation and linked list representation.
i. Array Representation
This method stores the tree data by scanning elements of nodes using level order fashion. So
it stores nodes level by level. If some element is missing, it leaves a blank space for it.
Example
UU-MTH- 1005 Discrete Mathematics Page 6
Represent the following binary tree in computer memory using the array representation
method.
Solution
Position 1 is holding the root, it has two children 5 and 16, they are placed at location 2 and 3. Some
children are missing, so their places are left blank.
Under this representation, the positions of two children for each node may be gotten by using the
following formulae:
child1_position = 2∗parent_position
child2_position =(2∗parent_position) + 1
To get parent’s position from child we have to follow this formula:
𝐶ℎ𝑖𝑙𝑑_𝑃𝑜𝑠𝑖𝑡𝑖𝑜𝑛
Parent_position = [ ]
2
Note: This approach is good, and easily we can find the positions of parent and child, but it is not
memory efficient. It will occupy many spaces that has no use. This representation is good for
complete binary tree.
UU-MTH- 1005 Discrete Mathematics Page 7
ii. Linked List Representation
Using this method, a binary tree is represented using a double linked list. In a double linked
list, every node consists of three fields. First field for storing left child address, second for
storing actual data and third for storing right child address.
Example
Represent the following binary tree in computer memory using the linked list representation
method.
Solution:
UU-MTH- 1005 Discrete Mathematics Page 8
Section 3: Traversing Binary Trees
As we already saw, traversing a binary tree means to visit all its nodes and this can be done using three
standard methods, namely, the preorder traversal, the postorder traversal and the inorder traversal.
The Preorder Traversal: this is a recursive process which follows the following steps to
complete:
i. first step, visit the root of the tree,
ii. second step, traverse the left subtree in preorder,
iii. and third step, traverse the right subtree in preorder.
The Postorder Traversal: this is a recursive process which follows the following steps to
complete:
i. first step, traverse the left subtree in postorder,
ii. second step, traverse the right subtree in postorder,
iii. and third step, visit the root of the tree.
The Inorder Traversal: this is a recursive process which follows the following steps to
complete:
i. first step, traverse in inorder the left subtree,
ii. second step, visit the root of the tree,
iii. and third step, traverse in inorder the right subtree.
Example
For the given binary tree below, determine its preorder, postorder and inorder traversal.
UU-MTH- 1005 Discrete Mathematics Page 9
Solution:
Section 4: Binary Search Tree
This is a type of binary trees characterized by nodes smaller than those pointing to them, on the left, and
by nodes larger than those pointing to them on the right. This is not necessarily that a node point to the
nodes whose values immediately precede and follow it.
Example (of a binary search tree)
Section 4.1: Algorithm for Searching and Inserting in Binary Search
Trees
UU-MTH- 1005 Discrete Mathematics Page 10
Given a binary search tree T, the following is an algorithm for inserting a piece of information INFO in
it:
i. Compare INFO with the root node.
ii. If INFO>ROOT NODE, proceed to the right child, and it becomes a root node for the right subtree.
iii. If INFO<ROOT NODE, proceed to the left child.
iv. Repeat the above steps until we meet a node which has no left and right subtree.
v. Now if INFO is greater than the node, then INFO is inserted as the right child, and if INFO is less than the node,
then the INFO is inserted as the left child.
Example
Show the binary search tree after inserting 3, 1,4,6,9,2,5,7 into an initially empty binary search tree.
Solution:
UU-MTH- 1005 Discrete Mathematics Page 11
Section 4.2: Algorithm for Deleting in Binary Search Trees
Given a binary search tree T, to delete a given INFO from it we have three cases, depending upon the
number of children of the deleted node:
i. Deleted Node has no children: We delete a node with no children by replacing the node with
null.
ii. Deleted Node has Only one child: Replace the value of a deleted node with the only child.
iii. Deletion node has only two children: In this case, replace the deleted node with the node that
is closest in the value to the deleted node. To find the nearest value, we move once to the left
and then to the right as far as possible. This node is called the immediate predecessor. Now
replace the value of the deleted node with the immediate predecessor and then delete the
replaced node by using case i or case ii.
Example
Show the binary search tree, given in the previous example, after deleting the root node.
Solution:
To delete the root node, first replace the root node with the closest elements of the root. For this, first,
move one step left and then to the right as far as possible to the node. Then delete the replaced node.
The tree after deletion is
UU-MTH- 1005 Discrete Mathematics Page 12
Bibliography
Chakraborty A. (2019). Binary Tree Representation in Data Structures.
Tutorials Point (I) Pvt. Ltd
Gersting J. L. (2014). Mathematical Structures for Computer Science (7th ed.).
W.H. Freeman and Company.
JavaTPoint (JTP, 2018). Binary Trees. Java T Point.
Rosen K. H. (2011). Discrete Mathematics and its applications (7th ed.).
McGraw Hill Education (India) Private Limited
Susanna S. E. (2010). Discrete Mathematics with Applications. (4th ed.).
Brooks/Cole Cengage Learning
TutorialsPoint (TP, 2016). Graph Theory. Tutorials Point (I) Pvt. Ltd
Wallis W. D. (2012). A Beginner’s Guide to Discrete Mathematics. (2nd ed.).
Birkhauser.
UU-MTH- 1005 Discrete Mathematics Page 13
