UNIT- V

 Tree is a hierarchical data structure which stores the information naturally in the form of
hierarchy style.
 Tree is one of the most powerful and advanced data structures.
 It is a non-linear data structure compared to arrays, linked lists, stack and queue.
 It represents the nodes connected by edges.

The above figure represents structure of a tree. Tree has 2 subtrees.

A is a parent of B and C.
B is called a child of A and also parent of D, E, F.

Tree is a collection of elements called Nodes, where each node can have arbitrary number of
children.

Field Description
Root Root is a special node in a tree. The entire tree is referenced through it. It does not
have a parent.
Parent Node Parent node is an immediate predecessor of a node.
Child Node All immediate successors of a node are its children.
Siblings Nodes with the same parent are called Siblings.
Path Path is a number of successive edges from source node to destination node.
Height of Node Height of a node represents the number of edges on the longest path between that
node and a leaf.
Height of Tree Height of tree represents the height of its root node.
Depth of Node Depth of a node represents the number of edges from the tree's root node to the
node.
Degree of Node Degree of a node represents a number of children of a node.
Edge Edge is a connection between one node to another. It is a line between two nodes or
a node and a leaf.

In the above figure, D, F, H, G are leaves. B and C are siblings. Each node excluding a root
is connected by a direct edge from exactly one other node
parent → children.
Advantages of Tree
 Tree reflects structural relationships in the data.
 It is used to represent hierarchies.
 It provides an efficient insertion and searching operations.
 Trees are flexible, It allows to move subtrees around with minimum effort.

Binary Tree
 Binary Tree is a special data structure used for data storage purposes.
 A binary tree has a special condition that each node can have a maximum of two
children.
 A binary tree has the benefits of both an ordered array and a linked list as search is as
quick as in a sorted array and insertion or deletion operation are as fast as in linked
list.

Binary Tree Traversals

 When we wanted to display a binary tree, we need to follow some order in which all
the nodes of that binary tree must be displayed.
 In any binary tree, displaying order of nodes depends on the traversal method.

Displaying (or) visiting order of nodes in a binary tree is called as Binary Tree
Traversal.

There are three types of binary tree traversals.

1. In - Order Traversal
2. Pre - Order Traversal
3. Post - Order Traversal
Consider the following Binary tree

1. In - Order Traversal ( leftChild - root - rightChild )

In In-Order traversal, the root node is visited between the left child and right child. 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. This in-order traversal is applicable for every root node of all
subtrees in the tree. This is performed recursively for all nodes in the tree.
In the above example of a binary tree, first we try to visit left child of root node 'A', but A's
left child 'B' is a root node for left subtree. so we try to visit its (B's) left child 'D' and again D
is a root for subtree with nodes D, I and J. So we try to visit its left child 'I' and it is the
leftmost child. So first we visit 'I' then go for its root node 'D' and later we visit D's right
child 'J'. With this we have completed the left part of node B. Then visit 'B' and next B's
right child 'F' is visited. With this we have completed left part of node A. Then visit root
node 'A'. With this we have completed left and root parts of node A. Then we go for the right
part of the node A. In right of A again there is a subtree with root C. So go for left child of C
and again it is a subtree with root G. But G does not have left part so we visit 'G' and then
visit G's right child K. With this we have completed the left part of node C. Then visit root
node 'C' and next visit C's right child 'H' which is the rightmost child in the tree. So we stop
the process.

That means here we have visited in the order of I - D - J - B - F - A - G - K - C - H using In-

Order Traversal.

In-Order Traversal for above example of binary tree is

I-D-J-B-F-A-G-K-C-H

2. Pre - Order Traversal ( root - leftChild - rightChild )

In Pre-Order traversal, the root node is visited before the left child and right child nodes. In
this traversal, the root node is visited first, then its left child and later its right child. This pre-
order traversal is applicable for every root node of all subtrees in the tree.
In the above example of binary tree, first we visit root node 'A' then visit its left
child 'B' which is a root for D and F. So we visit B's left child 'D' and again D is a root for I
and J. So we visit D's left child 'I' which is the leftmost child. So next we go for visiting D's
right child 'J'. With this we have completed root, left and right parts of node D and root, left
parts of node B. Next visit B's right child 'F'. With this we have completed root and left parts
of node A. So we go for A's right child 'C' which is a root node for G and H. After visiting C,
we go for its left child 'G' which is a root for node K. So next we visit left of G, but it does
not have left child so we go for G's right child 'K'. With this, we have completed node C's
root and left parts. Next visit C's right child 'H' which is the rightmost child in the tree.

So we stop the process.

That means here we have visited in the order of A-B-D-I-J-F-C-G-K-H using Pre-Order
Traversal.

Pre-Order Traversal for above example binary tree is

A-B-D-I-J-F-C-G-K-H

3. Post - Order Traversal ( leftChild - rightChild - root )

In Post-Order traversal, the root node is visited after left child and right child. 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.

Here we have visited in the order of I - J - D - F - B - K - G - H - C - A using Post-Order

Traversal.

Post-Order Traversal for above example binary tree is

I-J-D-F-B-K-G-H-C-A

Binary Search Tree Operations

Following are the operations performed on binary search tree:

1. Insert Operation
 Insert operation is performed with O(log n) time complexity in a binary search tree.
 Insert operation starts from the root node. It is used whenever an element is to be
inserted.

The following algorithm shows the insert operation in binary search tree:

Step 1: Create a new node with a value and set its left and right to NULL.
Step 2: Check whether the tree is empty or not.
Step 3: If the tree is empty, set the root to a new node.
Step 4: If the tree is not empty, check whether a value of new node is smaller or larger than
the node (here it is a root node).
Step 5: If a new node is smaller than or equal to the node, move to its left child.
Step 6: If a new node is larger than the node, move to its right child.
Step 7: Repeat the process until we reach to a leaf node.
2. Search Operation
 Search operation is performed with O(log n) time complexity in a binary search tree.
 This operation starts from the root node. It is used whenever an element is to be searched.

The following algorithm shows the search operation in binary search tree:

Step 1: Read the element from the user .

Step 2: Compare this element with the value of root node in a tree.
Step 3: If element and value are matching, display "Node is Found" and terminate the
function.
Step 4: If element and value are not matching, check whether an element is smaller or larger
than a node value.
Step 5: If an element is smaller, continue the search operation in left subtree.
Step 6: If an element is larger, continue the search operation in right subtree.
Step 7: Repeat the same process until we found the exact element.
Step 8: If an element with search value is found, display "Element is found" and terminate
the function.
Step 9: If we reach to a leaf node and the search value is not match to a leaf node, display
"Element is not found" and terminate the function.
GRAPHS
A graph is a pictorial representation of a set of objects where some pairs of objects are
connected by links. The interconnected objects are represented by points termed as vertices,
and the links that connect the vertices are called edges.
Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of
edges, connecting the pairs of vertices. Take a look at the following graph.

In the above graph,

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}

Elementary Graph Operations

Following are basic primary operations of a Graph −
 Add Vertex − Adds a vertex to the graph. 
 Add Edge − Adds an edge between the two vertices of the graph.
 Display Vertex − Displays a vertex of the graph.
Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses a
stack to remember to get the next vertex to start a search, when a dead end occurs in any
iteration.

As in the example given above, DFS algorithm traverses from S to A to D to G to E to B

first, then to F and lastly to C. It employs the following rules.
 Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a
stack.
  Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop
up all the vertices from the stack, which do not have adjacent vertices.)
 Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty. 

Step Traversal Description

Initialize the stack.

Mark S as visited and put it onto

the stack. Explore any unvisited
adjacent node from S. We have
three nodes and we can pick any
of them. For this example, we
shall take the node in an
alphabetical order.

Mark A as visited and put it onto

the stack. Explore any unvisited
adjacent node from A.
Both Sand D are adjacent
to A but we are concerned for
unvisited nodes only.
4

Visit D and mark it as visited and

put onto the stack. Here, we
have B and C nodes, which are
adjacent to D and both are
unvisited. However, we shall
again choose in an alphabetical
order.

We choose B, mark it as visited

and put onto the stack.
Here Bdoes not have any
unvisited adjacent node. So, we
pop Bfrom the stack.

We check the stack top for return

to the previous node and check if
it has any unvisited nodes. Here,
we find D to be on the top of the
stack.

Only unvisited adjacent node is

from D is C now. So we visit C,
mark it as visited and put it onto
the stack.
As C does not have any unvisited adjacent node so we keep popping the stack until we find
a node that has an unvisited adjacent node. In this case, there's none and we keep popping
until the stack is empty.
Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion and uses
a queue to remember to get the next vertex to start a search, when a dead end occurs in any
iteration.

As in the example given above, BFS algorithm traverses from A to B to E to F first then to C
and G lastly to D. It employs the following rules.
 Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in
a queue.
 Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue. 
 Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.

Step Traversal Description

Initialize the queue.

2

We start from
visiting S(starting node),
and mark it as visited.

3
We then see an unvisited
adjacent node from S. In
this example, we have
three nodes but
alphabetically we
choose A, mark it as
visited and enqueue it.

Next, the unvisited

adjacent node
from S is B. We mark it
as visited and enqueue it.

Next, the unvisited

adjacent node
from S is C. We mark it
as visited and enqueue it.
6

Now, S is left with no

unvisited adjacent nodes.
So, we dequeue and
find A.

From A we have D as
unvisited adjacent node.
We mark it as visited and
enqueue it.

At this stage, we are left with no unmarked (unvisited) nodes. But as per the algorithm we
keep on dequeuing in order to get all unvisited nodes. When the queue gets emptied, the
program is over.

Spanning Trees
A spanning tree is a subset of Graph G, which has all the vertices covered with minimum
possible number of edges. Hence, a spanning tree does not have cycles and it cannot be
disconnected.
By this definition, we can draw a conclusion that every connected and undirected Graph G
has at least one spanning tree. A disconnected graph does not have any spanning tree, as it
cannot be spanned to all its vertices.
We found three spanning trees off one complete graph. A complete undirected graph can
have maximum nn-2 number of spanning trees, where n is the number of nodes. In the above
addressed example, n is 3, hence 33−2 = 3 spanning trees are possible.

SEARCHING AND SORTING

SEARCHING
 Searching is a process of locating a particular element present in a given set of
elements.
 Searching Algorithms are designed to check for an element or retrieve an element
from any data structure where it is stored.
Based on the type of search operation, these algorithms are generally classified into two
categories:
1. Linear Search or Sequential Search
 Linear search is a very simple search algorithm.
 In this type of search, a sequential search is made over all items one by one.
 Every item is checked and if a match is found then that particular item is returned,
otherwise the search continues till the end of the data collection.
 Linear search is mostly used to search an unordered list of elements (array in which
data elements are not sorted).

Example
If an array A[] is declared and initialized as,

int A[] = {10, 8, 2, 7, 3, 4, 9, 1, 6, 5};

and the value to be searched is VAL = 7, then searching means to find whether the value
‘7’ is present in the array or not. If yes, then it returns the position of its occurrence. Here,
POS = 3 (index starting from 0).

2. Binary Search
 Binary search is a fast search algorithm.
 This search algorithm works on the principle of divide and conquer.
 For this algorithm to work properly, the data collection should be in the sorted form.
 Binary search looks for a particular item by comparing the middle most item of the
collection.
 If a match occurs, then the index of item is returned.
 If the middle item is greater than the item, then the item is searched in the sub-array to
the left of the middle item.
 Otherwise, the item is searched for in the sub-array to the right of the middle item.
 This process continues on the sub-array as well until the size of the subarray reduces
to zero.
Example
How Binary Search Works?
For a binary search to work, it is mandatory for the target array to be sorted. We shall learn
the process of binary search with a pictorial example. The following is our sorted array and
let us assume that we need to search the location of value 31 using binary search.

First, we shall determine half of the array by using this formula −

mid = low + (high - low) / 2
Here it is, 0 + (9 - 0 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

Now we compare the value stored at location 4, with the value being searched, i.e. 31. We
find that the value at location 4 is 27, which is not a match. As the value is greater than 27
and we have a sorted array, so we also know that the target value must be in the upper
portion of the array.

We change our low to mid + 1 and find the new mid value again.
low = mid + 1
mid = low + (high - low) / 2
Our new mid is 7 now. We compare the value stored at location 7 with our target value 31.

The value stored at location 7 is not a match, rather it is more than what we are looking for.
So, the value must be in the lower part from this location.

Hence, we calculate the mid again. This time it is 5.

We compare the value stored at location 5 with our target value. We find that it is a match.

We conclude that the target value 31 is stored at location 5.

Binary search halves the searchable items and thus reduces the count of comparisons to be
made to very less numbers.

SORTING
 Sorting refers to arranging data in a particular order or format.
 Sorting algorithm specifies the way to arrange data in a particular order.
 The importance of sorting lies in the fact that data searching can be optimized to a
very high level, if data is stored in a sorted manner.
 Sorting is also used to represent data in more readable formats.
Following are some of the examples of sorting in real-life scenarios −
 Telephone Directory − The telephone directory stores the telephone numbers of
people sorted by their names, so that the names can be searched easily.
 Dictionary − The dictionary stores words in an alphabetical order so that searching of
any word becomes easy.
Selection sort
 Selection sort is a simple sorting algorithm.
 This sorting algorithm is an in-place comparison-based algorithm in which the list is
divided into two parts, the sorted part at the left end and the unsorted part at the right
end.
 Initially, the sorted part is empty and the unsorted part is the entire list.
 The smallest element is selected from the unsorted array and swapped with the
leftmost element, and that element becomes a part of the sorted array.
 This process continues moving unsorted array boundary by one element to the right.
 This algorithm is not suitable for large data sets.

How Selection Sort Works?

Consider the following depicted array as an example.
For the first position in the sorted list, the whole list is scanned sequentially. The first
position where 14 is stored presently, we search the whole list and find that 10 is the lowest
value.

So we replace 14 with 10. After one iteration 10, which happens to be the minimum value in
the list, appears in the first position of the sorted list.

For the second position, where 33 is residing, we start scanning the rest of the list in a linear
manner.

We find that 14 is the second lowest value in the list and it should appear at the second
place. We swap these values.

After two iterations, two least values are positioned at the beginning in a sorted manner.

The same process is applied to the rest of the items in the array.
Following is a pictorial depiction of the entire sorting process −
Bubble sort or Exchange sort
 Bubble sort is a simple sorting algorithm.
 This sorting algorithm is comparison-based algorithm in which each pair of adjacent
elements is compared and the elements are swapped if they are not in order.
 This algorithm is not suitable for large data sets
How Bubble Sort Works?
We take an unsorted array for our example. Bubble sort takes Ο(n2) time so we're keeping it
short and precise.

Bubble sort starts with very first two elements, comparing them to check which one is
greater.

In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we
compare 33 with 27.
We find that 27 is smaller than 33 and these two values must be swapped.

The new array should look like this −

Next we compare 33 and 35. We find that both are in already sorted positions.

Then we move to the next two values, 35 and 10.

We know then that 10 is smaller 35. Hence they are not sorted.

We swap these values. We find that we have reached the end of the array. After one
iteration, the array should look like this −

To be precise, we are now showing how an array should look like after each iteration. After
the second iteration, it should look like this −

Notice that after each iteration, at least one value moves at the end.

And when there's no swap required, bubble sorts learns that an array is completely sorted.
Insertion Sort
 This is an in-place comparison-based sorting algorithm.
 Here, a sub-list is maintained which is always sorted.
 For example, the lower part of an array is maintained to be sorted.
 An element which is to be inserted in this sorted sub-list, has to find its appropriate
place and then it has to be inserted there.
 Hence the name, insertion sort.
 The array is searched sequentially and unsorted items are moved and inserted into the
sorted sub-list (in the same array).
 This algorithm is not suitable for large data sets.

How Insertion Sort Works?

We take an unsorted array for our example.

Insertion sort compares the first two elements.

It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted sub-list.

Insertion sort moves ahead and compares 33 with 27.

And finds that 33 is not in the correct position.

It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here we see that
the sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the sorted sub-
list remains sorted after swapping.

By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10.

These values are not in a sorted order.

So we swap them.

However, swapping makes 27 and 10 unsorted.

Hence, we swap them too.

Again we find 14 and 10 in an unsorted order.

We swap them again. By the end of third iteration, we have a sorted sub-list of 4 items.

This process goes on until all the unsorted values are covered in a sorted sub-list.

*******