UNIT – 3

Tree
A Tree is a recursive data structure containing the set of one or more data
nodes where one node is designated as the root of the tree while the
remaining nodes are called as the children of the root.

The nodes other than the root node are partitioned into the non empty
sets where each one of them is to be called sub-tree.

In a general tree, A node can have any number of children nodes but it
can have only a single parent.

The above figure shows a tree, where the node A is the root node of the
tree while the other nodes can be seen as the children of A.

Basic terminology
o Root Node: - The root node is the topmost node in the tree
hierarchy. In other words, the root node is the one which doesn't
have any parent.

o Sub Tree: - If the root node is not null, the tree T1, T2 and T3 is
called sub-trees of the root node.

o Leaf Node: - The node of tree, which doesn't have any child node,
is called leaf node. Leaf node is the bottom most node of the tree.
There can be any number of leaf nodes present in a general tree.
Leaf nodes can also be called external nodes.

o Path: - The sequence of consecutive edges is called path. In the

tree shown in the above image, path to the node E is A→ B → E.
1
Page
 o Ancestor node: - An ancestor of a node is any predecessor node
on a path from root to that node. The root node doesn't have any
ancestors. In the tree shown in the above image, the node F have
the ancestors, B and A.

o Siblings: - Nodes which belong to same Parent are called

as SIBLINGS. In simple words, the nodes with the same parent are
called Sibling nodes.
o Degree: - Degree of a node is equal to number of children, a node
have. In the tree shown in the above image, the degree of node B is
2. Degree of a leaf node is always 0 while in a complete binary tree,
degree of each node is equal to 2.

o Height: - The total number of edges from leaf node to a particular

node in the longest path is called as HEIGHT of that Node. In a
tree, height of the root node is said to be height of the tree. In a
tree, height of all leaf nodes is '0'.

o Level Number :- Each node of the tree is assigned a level number

in such a way that each node is present at one level higher than its
parent. Root node of the tree is always present at level 0.

General Tree
A Tree in which each node having either 0 or more child nodes is
called general tree.

In General Tree, each node can have infinite number of children. This tree
is the super-set of all other types of trees.
2
Page
 Binary Tree
A binary tree is a special type of tree data structure in which every node
can have a maximum of 2 children. One is known as a left child and the
other is known as right child.

In a binary tree, every node can have either 0 children or 1 child or 2

children but not more than 2 children.

Binary Tree representation

There are two types of representation of a binary tree:

1. Linked Representation

In this representation, the binary tree is stored in the memory, in the

form of a linked list where the number of nodes are stored at non-
contiguous memory locations and linked together by inheriting parent
child relationship like a tree. every node contains three parts : pointer to
the left node, data element and pointer to the right node. Each binary
tree has a root pointer which points to the root node of the binary tree. In
an empty binary tree, the root pointer will point to null.

Consider the binary tree given in the figure below.

In the above figure, a tree is seen as the collection of nodes where each
node contains three parts : left pointer, data element and right pointer.
3

Left pointer stores the address of the left child while the right pointer
Page
 stores the address of the right child. The leaf node contains null in its left
and right pointers.

2. Sequential Representation / Array representation

Binary tree using array represents a node which is numbered sequentially

level by level from left to right. Even empty nodes are numbered.

Location number of an array is used to store the size of the tree. The first
index of an array that is '0', stores the total number of nodes. All nodes
are numbered from left to right level by level from top to bottom. In a
tree, each node having an index i is put into the array as its ith element.

Value '7' is the total number of nodes. If any node does not have any of
its child, null value is stored at the corresponding index of the array.

Applications of Binary Tree

• Binary trees are used to represent a nonlinear data structure.

• One of the most important applications of the Binary tree is in the
searching algorithm.

Tree Traversal
Tree Traversal refers to the process of visiting each node in a tree data
structure exactly once.

Various tree traversal techniques are-

4
Page
 Depth First Traversal-

Following three traversal techniques fall under Depth First Traversal-

1. Preorder Traversal

2. Inorder Traversal

3. Postorder Traversal

1. Preorder Traversal

In this traversal, the root node is visited first, then its left child and later
its right child.

Root → Left → Right

Algorithm-

1. Visit the root

2. Traverse the left sub tree i.e. call Preorder (left sub tree)

3. Traverse the right sub tree i.e. call Preorder (right sub tree)

Example-

Preorder Traversal Shortcut

5

Traverse the entire tree starting from the root node keeping yourself to
Page

the left.
 2. Inorder Traversal

In this traversal, the left child node is visited first, then the root node is
visited and later we go for visiting the right child node.

Left → Root → Right

Algorithm-

1. Traverse the left sub tree i.e. call Inorder (left sub tree)

2. Visit the root

3. Traverse the right sub tree i.e. call Inorder (right sub tree)

Example-

Inorder Traversal Shortcut

Keep a plane mirror horizontally at the bottom of the tree and take the
projection of all the nodes.
6
Page
 3. Postorder Traversal

In this traversal, left child node is visited first, then its right child and
then its root node. This is recursively performed until the right most node
is visited.

Left → Right → Root

Algorithm-

1. Traverse the left sub tree i.e. call Postorder (left sub tree)

2. Traverse the right sub tree i.e. call Postorder (right sub tree)

3. Visit the root

Example-
7
Page
 Postorder Traversal Shortcut

Pluck all the leftmost leaf nodes one by one.

Breadth First Traversal-

• Breadth First Traversal of a tree prints all the nodes of a tree level
by level.

• Breadth First Traversal is also called as Level Order Traversal.

Example-

Binary Search Tree (BST)

Binary Search Tree is a special kind of binary tree in which nodes are
arranged in a specific order. This is also called ordered binary tree.

1. In a binary search tree(BST), the value of all the nodes in the left
sub-tree is less than the value of the root.
8
Page
 2. Similarly, value of all the nodes in the right sub-tree is greater than
or equal to the value of the root.
3. This rule will be recursively applied to all the left and right sub-trees
of the root.

Binary Search Tree Construction-

Let us understand the construction of a binary search tree using the

following example-

Example-

Construct a Binary Search Tree (BST) for the following sequence of

numbers-

50, 70, 60, 20, 90, 10, 40, 100

When elements are given in a sequence,

• Always consider the first element as the root node.

• Consider the given elements and insert them in the BST one by one.

The binary search tree will be constructed as explained below-

Insert 50-

Insert 70-

• As 70 > 50, so insert 70 to the right of 50.

9
Page
 Insert 60-

• As 60 > 50, so insert 60 to the right of 50.

• As 60 < 70, so insert 60 to the left of 70.

Insert 20-

• As 20 < 50, so insert 20 to the left of 50.

Insert 90-

• As 90 > 50, so insert 90 to the right of 50.

• As 90 > 70, so insert 90 to the right of 70.
10
Page
 Insert 10-

• As 10 < 50, so insert 10 to the left of 50.

• As 10 < 20, so insert 10 to the left of 20.

Insert 40-

• As 40 < 50, so insert 40 to the left of 50.

• As 40 > 20, so insert 40 to the right of 20.

Insert 100-

• As 100 > 50, so insert 100 to the right of 50.

• As 100 > 70, so insert 100 to the right of 70.
• As 100 > 90, so insert 100 to the right of 90.
11

This is the required Binary Search Tree.

Page
 Operations on Binary Search Tree
There are many operations which can be performed on a binary search
tree.

1. Search Operation
2. Insertion Operation
3. Deletion Operation

Search Operation
Search Operation is performed to search a particular element in the
Binary Search Tree.

Rules-
1. Compare the element with the root of the tree.
2. If the item is matched then return the location of the node.
3. Otherwise check if item is less than the element present on root, if
so then move to the left sub-tree.
4. If not, then move to the right sub-tree.
5. Repeat this procedure recursively until match found.
6. If element is not found then return NULL.

Example-
Consider key = 45 has to be searched in the given BST-

• We start our search from the root node 25.

• As 45 > 25, so we search in 25’s right subtree.
• As 45 < 50, so we search in 50’s left subtree.
• As 45 > 35, so we search in 35’s right subtree.
• As 45 > 44, so we search in 44’s right subtree but 44 has no
subtrees.
12

• So, we conclude that 45 is not present in the above BST.

Page
 Insertion Operation

Insertion Operation is performed to insert an element in the Binary

Search Tree.

Rules-
The insertion of a new key always takes place as the child of some leaf
node.

For finding out the suitable leaf node,

• Search the key to be inserted from the root node till some leaf node
is reached.
• Once a leaf node is reached, insert the key as child of that leaf
node.

Example-
Consider the following example where key = 40 is inserted in the given
BST-

• We start searching for value 40 from the root node 100.

• As 40 < 100, so we search in 100’s left subtree.
• As 40 > 20, so we search in 20’s right subtree.
• As 40 > 30, so we add 40 to 30’s right subtree.

Deletion Operation
Deletion Operation is performed to delete a particular element from the
Binary Search Tree.

When it comes to deleting a node from the binary search tree, following
three cases are possible-

Case-01: Deletion Of A Node Having No Child (Leaf Node)-

Just remove / disconnect the leaf node that is to be deleted from the tree.

Example-

Consider the following example where node with value = 20 is deleted

13

from the BST-

Page
 Case-02: Deletion Of A Node Having Only One Child-

Just make the child of the deleting node, the child of its grandparent.

Example-

Consider the following example where node with value = 30 is deleted

from the BST-

Case-03: Deletion Of A Node Having Two Children-

A node with two children may be deleted from the BST in the following
two ways-

Method-01:

• Visit to the right subtree of the deleting node.

• Pluck the least value element called as inorder successor.
• Replace the deleting element with its inorder successor.

Example-

Consider the following example where node with value = 15 is deleted

from the BST-
14
Page
 Method-02:
• Visit to the left subtree of the deleting node.
• Pluck the greatest value element called as inorder predecessor.
• Replace the deleting element with its inorder predecessor.

Example-
Consider the following example where node with value = 15 is deleted
from the BST-

Heap Tree
Heap is a tree-based data structure in which all nodes in the tree are in
the specific order.

Heap is a binary tree with special characteristics. In a heap data

structure, nodes are arranged based on their values. A heap data
structure sometimes also called as Binary Heap.

There are two types of heap data structures and they are as follows...

1. Max Heap
2. Min Heap

Every heap data structure has the following properties...

15

Property #1 (Ordering): Nodes must be arranged in an order according

to their values based on Max heap or Min heap.
Page
 Property #2 (Structural): All levels in a heap must be full except the
last level and all nodes must be filled from left to right strictly.

1. Max Heap
Max heap is a specialized full binary tree in which every parent node
contains greater or equal value than its child nodes.

2. Min-Heap –In mean heap, the value of the root node is less than
or equal to either of its children.

Methods or Operations of Heap

• find - find an item in a heap.

• insert - add an item in a heap ensuring the heap property is
maintained min-heap and max-heap property.
• delete - remove an item in a heap.
• extract - return the value of an item and then delete from heap.
• replace - extract or pop the root and insert or push a new item in a
heap ensuring the heap property has maintained min-heap and
max-heap property.

AVL Tree:
16

AVL tree is a height balanced binary search tree. That means, an AVL tree
Page

is also a binary search tree but it is a balanced tree.

 A binary tree is said to be balanced if, the difference between the heights
of left and right subtrees of every node in the tree is either -1, 0 or +1.

In other words, a binary tree is said to be balanced if the height of left

and right children of every node differ by either -1, 0 or +1.

In an AVL tree, every node maintains an extra information known

as balance factor.

The AVL tree was introduced in the year 1962 by G.M. Adelson-Velsky
and E.M. Landis.

An AVL tree is defined as follows...

An AVL tree is a balanced binary search tree. In an AVL tree,
balance factor of every node is either -1, 0 or +1.
Balance factor of a node is the difference between the heights of left and
right subtrees of that node. The balance factor of a node is calculated
either height of left subtree - height of right subtree (OR) height of
right subtree - height of left subtree.
In the following explanation, we calculate as follows...
Balance factor = heightOfLeftSubtree - heightOfRightSubtree

If balance factor of any node is 1, it means that the left sub-tree is

one level higher than the right sub-tree.
If balance factor of any node is 0, it means that the left sub-tree
and right sub-tree contain equal height.
If balance factor of any node is -1, it means that the left sub-tree is
one level lower than the right sub-tree.

Example:
17
Page
 The above tree is a binary search tree and every node is satisfying
balance factor condition. So this tree is said to be an AVL tree.

Every AVL Tree is a binary search tree but every Binary Search Tree need not
be AVL tree.

M-Way
Way Search Tree
The m-way search trees are multi multi-way
way trees which are generalised
versions of binary trees,, where each node contains multiple elements.

In an m-Way
Way tree of order m,, each node contains a maximum of
m – 1 elements (key) and m childrens (pointers).

M-way
way Search tree Properties:
Properties

1. Each node can point

poin at most m sub-tree.
2. The number of keys in each node is maximum m-1m 1 and each node
can have maximum m pointers.
3. The keys in each node are in ascending order.

Representation of M-way
M Search tree:

In the structure, P0, P1, P2, .... , Pn are pointers to the node’s sub-trees
sub and
K0, K1, K2, .... , Kn-1 are the key values of the node. All the key values are
stored in ascending order. That is Ki < Ki+1 for 0 ≤ i ≤ n-2.

Example of 3-way
way search tree:
18
Page
 UNIT-4
What is sorting?

Sorting is a process of ordering or placing a list of elements from a

collection in some kind of order.
It is nothing but storage of data in sorted order.
Sorting can be done in ascending and descending order.
It arranges the data in a sequence which makes searching easier.

Importance of sorting

• To represent data in more readable format.

• Optimize data searching to high level.

Different Sorting Algorithms

There are many different techniques available for sorting, differentiated
by their efficiency and space requirements.
The most common sorting algorithms are:
• Bubble Sort
• Exchange sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Radix sort
• Heap Sort

Bubble Sort
In Bubble sort, Each element of the array is compared with its adjacent
element. The algorithm processes the list in passes. A list with n elements
requires n-1 passes for sorting.

Consider an array A of n elements whose elements are to be sorted by

using Bubble sort.

The algorithm processes like following.

1. In Pass 1, A[0] is compared with A[1], A[1] is compared with A[2],

A[2] is compared with A[3] and so on. At the end of pass 1, the
largest element of the list is placed at the highest index of the list.

2. In Pass 2, A[0] is compared with A[1], A[1] is compared with A[2]

and so on. At the end of Pass 2 the second largest element of the
19

list is placed at the second highest index of the list.

Page
 3. In pass n-1, A[0] is compared with A[1], A[1] is compared with
A[2] and so on. At the end of this pass. The smallest element of the
list is placed at the first index of the list.

Algorithm :
o Step 1: Repeat Step 2 For i = 0 to N-1
o Step 2: Repeat For J = i + 1 to N - 1
o Step 3: IF A[J] > A[i]
SWAP A[J] and A[i]
[END OF INNER LOOP]
[END OF OUTER LOOP
o Step 4: EXIT

Example 1: Suppose we have a list of array of 5 elements

A[5]={40,50,30,20,10}. We have to sort this array using bubble sort
algorithm.

Example 2:

Exchange Sort

The exchange sort is almost similar as the bubble sort.

The exchange sort compares each element of an array and swap those
20

elements that are not in their proper position,

Page
 just like a bubble sort does. The only difference between the two
sorting algorithms is the manner in which they compare the elements.
The exchange sort compares the first element with each element of the
array, making a swap where is necessary.
In some situations the exchange sort is slightly more efficient than its
counter part the bubble sort. The bubble sort needs a final pass to
determine that it is finished, thus is slightly less efficient than the
exchange sort, because the exchange sort doesn’t need a final pass.

Example:

Let's examine our same table of elements again using an exchange sort for
descending order.

Remember, a "pass" is defined as one full trip through the array comparing and if
necessary, swapping elements

Array at beginning: 84 69 76 86 94 91
After Pass #1: 94 69 76 84 86 91
After Pass #2: 94 91 69 76 84 86
After Pass #3: 94 91 86 69 76 84
After Pass #4: 94 91 86 84 69 76
After Pass #5 (done): 94 91 86 84 76 69

Selection Sort
In selection sort, the smallest value among the unsorted elements of the
array is selected in every pass and inserted to its appropriate position into
the array.

First, find the smallest element of the array and place it on the first
position. Then, find the second smallest element of the array and place it
on the second position. The process continues until we get the sorted
array.

The array with n elements is sorted by using n-1 pass of selection sort
algorithm.

Algorithm:

Step 1 - Select the first element of the list (i.e., Element at first position
in the list).

Step 2: Compare the selected element with all the other elements in the
21

list.
Page
 Step 3: In every comparison, if any element is found smaller than the
selected element (for Ascending order), then both are swapped.

Step 4: Repeat the same procedure with element in the next position in
the list till the entire list is sorted.

Example:

Assume that the array A=[7,5,4,2] needs to be sorted in ascending order.

Insertion Sort
Insertion sort works in the similar way as we sort cards in our hand in a
card game.

In insertion sort algorithm, every iteration moves an element from

unsorted portion to sorted portion until all the elements are sorted in the
list.

This is less efficient than the other sort algorithms like quick sort, merge
sort, etc.

Algorithm:

Step 1 - Assume that first element in the list is in sorted portion and all
the remaining elements are in unsorted portion.

Step 2: Take first element from the unsorted portion and insert that
element into the sorted portion in the order specified.

Step 3: Repeat the above process until all the elements from the
unsorted portion are moved into the sorted portion.
22
Page
23
Page
Example:
 Merge Sort
Merge sort is one of the most efficient sorting algorithms. It works on the
principle of Divide and Conquer.

Merge sort repeatedly breaks down a list into several sublists until each
sublist consists of a single element and merging those sublists in a
manner that results into a sorted list.

The concept of Divide and Conquer involves three steps:

1. Divide the problem into multiple small problems.

2. Conquer the subproblems by solving them. The idea is to break

down the problem into atomic subproblems, where they are actually
solved.

3. Combine the solutions of the subproblems to find the solution of the

actual problem.

In merge sort we follow the following steps:

1. We take a variable p and store the starting index of our array in

this. And we take another variable r and store the last index of
array in it.
2. Then we find the middle of the array using the formula
(p + r)/2 and mark the middle index as q, and break the array
into two subarrays, from p to q and from q + 1 to r index.
3. Then we divide these 2 subarrays again, just like we divided our
main array and this continues.
24

4. Once we have divided the main array into subarrays with single
Page

elements, then we start merging the subarrays.

25
Page Example: Let's consider an array with values {14, 7, 3, 12, 9, 11, 6, 12}
 Quick Sort

Quick sort is a fast sorting algorithm used to sort a list of elements. Quick
sort algorithm is invented by C. A. R. Hoare.

The quick sort algorithm attempts to separate the list of elements into

two parts and then sort each part recursively. That means it use divide

and conquer strategy. In quick sort, the partition of the list is performed

based on the element called pivot. Here pivot element is one of the
elements in the list.

The list is divided into two partitions such that "all elements to the left

of pivot are smaller than the pivot and all elements to the right of
pivot are greater than or equal to the pivot".

Step by Step Process

In Quick sort algorithm, partitioning of the list is performed using

following steps...

• Step 1 - Consider the first element of the list as pivot (i.e.,

Element at first position in the list).

• Step 2 - Define two variables i and j. Set i and j to first and last
elements of the list respectively.

• Step 3 - Increment i until list[i] > pivot then stop.

• Step 4 - Decrement j until list[j] < pivot then stop.

• Step 5 - If i < j then exchange list[i] and list[j].

• Step 6 - Repeat steps 3,4 & 5 until i > j.

• Step 7 - Exchange the pivot element with list[j] element.

Example:
26
Page
Page 27
 Radix Sort
Radix sort is one of the sorting algorithms used to sort a list of integer
numbers in order. In radix sort algorithm, a list of integer numbers will be
sorted based on the digits of individual numbers. Sorting is performed
from least significant digit to the most significant digit.

Radix sort algorithm requires the number of passes which are equal to the
number of digits present in the largest number among the list of
numbers. For example, if the largest number is a 3 digit number then that
list is sorted with 3 passes.

Step by Step Process

The Radix sort algorithm is performed using the following steps...

Step 1 - Define 10 queues each representing a bucket for each digit from
0 to 9.

Step 2 - Consider the least significant digit of each number in the list
which is to be sorted.

Step 3 - Insert each number into their respective queue based on the
least significant digit.

Step 4 - Group all the numbers from queue 0 to queue 9 in the order they
have inserted into their respective queues.

Step 5 - Repeat from step 3 based on the next least significant digit.

Step 6 - Repeat from step 2 until all the numbers are grouped based on
the most significant digit.

Example:
28
Page
 Heap Sort
Heap sort is one of the sorting algorithms used to arrange a list of
elements in order. Heapsort algorithm uses one of the tree concepts
called Heap Tree.

In this sorting algorithm, we use Max Heap to arrange list of elements in

Descending order and Min Heap to arrange list elements in Ascending
29

order.
Page
 Step by Step Process

The Heap sort algorithm to arrange a list of elements in ascending order

is performed using following steps...

Step 1 - Construct Heap Tree

Descending----(Max Heap)

Ascending----(Min Heap)

Step 2 - Delete root node and replace it with last leaf node of tree.

Step 3 - Put the deleted element into the Sorted list.

Step 4 – Heapify Tree

Step 5 – Repeat step 2 to 4 until heap remains with single element.

Step 6 - Display the sorted list.

Example: Consider an unsorted list: 45, 33, 3, 17, 25, 80

Max Heap

Step-1:

Spep-2: Delete root node (80) and replace it with the last leaf node (3).

Step 3:
30
Page
 Step-4: Heapify Tree

Now Repeat step 2 to 4 until heap remains with single element

Delete root node (45) and replace it with the last leaf node (25).

Heapify Tree

Delete root node (33) and replace it with the last leaf node (17).
31

Now Heapify Tree

Page
 Delete root node (25) and replace it with the last leaf node (3).

Now Heapify Tree

Delete root node (17) and replace it with the last leaf node (3).

Now we have a single element left in heap tree, So directly We put into
the sorted list.

Now the Final Sorted List in descending order is:

What is Search?
Search is a process of finding a value in a list of values. In other words,
searching is the process of locating given value position in a list of values.
32
Page
 Linear Search
Linear search is a very basic and simple search algorithm. In Linear
search, we search an element or value in a given array by traversing the
array from the starting, till the desired element or value is found.
It compares the element to be searched with all the elements present in
the array and when the element is matched successfully, it returns the
index of the element in the array, else it return -1.
Linear Search is applied on unsorted or unordered lists, when there are
fewer elements in a list.
Linear Search Algorithm:

Step 1 - Read the search element from the user.

Step 2 - Compare the search element with the first element in the list.

Step 3 - If both are matched, then display "Given element is found!!!" and
terminate the function

Step 4 - If both are not matched, then compare search element with the
next element in the list.

Step 5 - Repeat steps 3 and 4 until search element is compared with last
element in the list.

Step 6 - If last element in the list also doesn't match, then display
"Element is not found!!!" and terminate the function.

Example
Consider the following list of elements and the element to be searched...
33
Page
Page 34
 Binary Search
Binary search is a fast search algorithm. This search algorithm works on
the principle of divide and conquer. Binary Search is used with sorted
array or list.
Binary Search Algorithm:

Step 1 - Read the search element from the user.

Step 2 - Find the middle element in the sorted list.

Step 3 - Compare the search element with the middle element in the
sorted list.

Step 4 - If both are matched, then display "Given element is found!!!"

and terminate the function.

Step 5 - If both are not matched, then check whether the search element
is smaller or larger than the middle element.

Step 6 - If the search element is smaller than middle element, repeat

steps 2, 3, 4 and 5 for the left sublist of the middle element.

Step 7 - If the search element is larger than middle element, repeat

steps 2, 3, 4 and 5 for the right sublist of the middle element.

Step 8 - Repeat the same process until we find the search element in the
list or until sublist contains only one element.

Step 9 - If that element also doesn't match with the search element, then
display "Element is not found in the list!!!" and terminate the function.

Example
Consider the following list of elements and the element to be searched...
35
Page
Page 36