BABA MASTNATH UNIVERSITY
(Asthal Bohar, Rohtak)
(SESSION :- 2023-2025)
PRACTICLE FILE OF DATA
STRUCTURE
SUBMITTED TO :- SUBMITTED BY :-
DR. REENA NAME :- MONIKA
BMU ROHTAk CLASS :- MCA 2ND SEM.
ROLL NO. :-
DEPARTMENT OF COMPUTER SCIENCE AND
APPLICATIONS
FACULTY OF MANAGEMENT AND COMMERCE
INDEX
Sr. No. Topics Signature
1. Write a program to perform a binary search for a
given set of integer values.
2. Write a program to implement insert operation on
binary search tree.
3. Write a program to perform a Linear search for a
given set of integer values.
4. Write a program to implement delete operation on
binary search tree.
5. Write a program to implement Merge sort for the
given list of integer value.
6. Write a program to find minimum cost spanning tree
using Prim’s algorithms.
7. Write a program to find minimum cost spanning tree
using Kruskal’s algorithms.
8. Write a program to implement Quick sort for the
given list of integer values.
9. Write a program to sort the elements by using heap
sort.
10. Write a program to implement Search operation on
Binary Search Tree.
1. Write a program to perform a binary search for a given set
of integer values:
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, key):
if not self.root:
self.root = TreeNode(key)
else:
self._insert_recursive(self.root, key)
def _insert_recursive(self, node, key):
if key < node.key:
if node.left is None:
node.left = TreeNode(key)
else:
self._insert_recursive(node.left, key)
elif key > node.key:
if node.right is None:
node.right = TreeNode(key)
else:
self._insert_recursive(node.right, key)
def search(self, key):
return self._search_recursive(self.root, key)
def _search_recursive(self, node, key):
if node is None:
return False
elif node.key == key:
return True
elif key < node.key:
return self._search_recursive(node.left, key)
else:
return self._search_recursive(node.right, key)
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# Example usage:
if __name__ == "__main__":
bst = BinarySearchTree()
keys = [7, 4, 9, 2, 5, 8, 11]
for key in keys:
bst.insert(key)
print("Binary Search Tree:")
print(" 7")
print(" / \\")
print(" 4 9")
print(" / \\ / \\")
print(" 2 5 8 11")
target = 5
if bst.search(target):
print(f"\nElement {target} found in the binary search tree.")
else:
print(f"\nElement {target} not found in the binary search tree.")
Output:
Binary Search Tree:
7
/ \
4 9
/\ /\
2 5 8 11
Element 5 found in the binary search tree.
2. Write a program to implement insert operation on binary search
tree.
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, key):
if self.root is None:
self.root = TreeNode(key)
else:
self._insert_recursive(self.root, key)
def _insert_recursive(self, node, key):
if key < node.key:
if node.left is None:
node.left = TreeNode(key)
else:
self._insert_recursive(node.left, key)
elif key > node.key:
if node.right is None:
node.right = TreeNode(key)
else:
self._insert_recursive(node.right, key)
def inorder_traversal(self):
self._inorder_recursive(self.root)
def _inorder_recursive(self, node):
if node is not None:
self._inorder_recursive(node.left)
print(node.key, end=" ")
self._inorder_recursive(node.right)
# Example usage:
if __name__ == "__main__":
bst = BinarySearchTree()
keys = [7, 4, 9, 2, 5, 8, 11]
for key in keys:
bst.insert(key)
print("Binary Search Tree after insertion:")
bst.inorder_traversal()
Output:
Binary Search Tree after insertion:
2 4 5 7 8 9 11
3. Write a program to perform a Linear search for a given set of integer
values.
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # Target found, return its index
return -1 # Target not found
# Example usage:
arr = [3, 6, 2, 9, 5, 1, 8]
target = 5
result = linear_search(arr, target)
if result != -1:
print(f"Element {target} found at index {result}")
else:
print(f"Element {target} not found in the list")
Output:
Element 5 found at index 4
4. Write a program to implement delete operation on binary search
tree.
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, key):
if self.root is None:
self.root = TreeNode(key)
else:
self._insert_recursive(self.root, key)
def _insert_recursive(self, node, key):
if key < node.key:
if node.left is None:
node.left = TreeNode(key)
else:
self._insert_recursive(node.left, key)
elif key > node.key:
if node.right is None:
node.right = TreeNode(key)
else:
self._insert_recursive(node.right, key)
def delete(self, key):
self.root = self._delete_recursive(self.root, key)
def _delete_recursive(self, node, key):
if node is None:
return node
if key < node.key:
node.left = self._delete_recursive(node.left, key)
elif key > node.key:
node.right = self._delete_recursive(node.right, key)
else:
if node.left is None:
return node.right
elif node.right is None:
return node.left
# Node to be deleted has two children
successor_parent = node
successor = node.right
while successor.left:
successor_parent = successor
successor = successor.left
# Replace the value of the node to be deleted with the successor
value
node.key = successor.key
# Delete the successor node
if successor_parent.left == successor:
successor_parent.left = self._delete_recursive(successor,
successor.key)
else:
successor_parent.right = self._delete_recursive(successor,
successor.key)
return node
def inorder_traversal(self):
self._inorder_recursive(self.root)
def _inorder_recursive(self, node):
if node is not None:
self._inorder_recursive(node.left)
print(node.key, end=" ")
self._inorder_recursive(node.right)
# Example usage:
if __name__ == "__main__":
bst = BinarySearchTree()
keys = [7, 4, 9, 2, 5, 8, 11]
for key in keys:
bst.insert(key)
print("Binary Search Tree before deletion:")
bst.inorder_traversal()
bst.delete(9)
print("\nBinary Search Tree after deletion of 9:")
bst.inorder_traversal()
Output:
Binary Search Tree before deletion:
2 4 5 7 8 9 11
Binary Search Tree after deletion of 9:
2 4 5 7 8 11
5. Write a program to implement Merge sort for the given list of
integer value.
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
# Merge the two sorted halves
i=j=k=0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
# Example usage:
arr = [12, 11, 13, 5, 6, 7]
print("Original array:", arr)
merge_sort(arr)
print("Sorted array:", arr)
Output:
Original array: [12, 11, 13, 5, 6, 7]
Sorted array: [5, 6, 7, 11, 12, 13]
6. Write a program to find minimum cost spanning tree using Prim’s
algorithms.
import sys
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]
def add_edge(self, u, v, weight):
self.graph[u][v] = weight
self.graph[v][u] = weight
def print_mst(self, parent):
print("Edge \tWeight")
for i in range(1, self.V):
print(parent[i], "-", i, "\t", self.graph[i][parent[i]])
def min_key(self, key, mst_set):
min_val = sys.maxsize
min_index = -1
for v in range(self.V):
if key[v] < min_val and mst_set[v] == False:
min_val = key[v]
min_index = v
return min_index
def prim_mst(self):
key = [sys.maxsize] * self.V
parent = [None] * self.V
key[0] = 0
mst_set = [False] * self.V
parent[0] = -1
for _ in range(self.V):
u = self.min_key(key, mst_set)
mst_set[u] = True
for v in range(self.V):
if self.graph[u][v] > 0 and mst_set[v] == False and key[v] >
self.graph[u][v]:
key[v] = self.graph[u][v]
parent[v] = u
self.print_mst(parent)
# Example usage:
g = Graph(5)
g.add_edge(0, 1, 2)
g.add_edge(0, 3, 6)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 8)
g.add_edge(1, 4, 5)
g.add_edge(2, 4, 7)
g.add_edge(3, 4, 9)
print("Minimum Spanning Tree using Prim's Algorithm:")
g.prim_mst()
Output:
Minimum Spanning Tree using Prim's Algorithm:
Edge Weight
0-1 2
1-2 3
0-3 6
1-4 5
7. Write a program to find minimum cost spanning tree using Kruskal’s
algorithms.
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, weight):
self.graph.append([u, v, weight])
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
x_root = self.find(parent, x)
y_root = self.find(parent, y)
if rank[x_root] < rank[y_root]:
parent[x_root] = y_root
elif rank[x_root] > rank[y_root]:
parent[y_root] = x_root
else:
parent[y_root] = x_root
rank[x_root] += 1
def kruskal_mst(self):
result = []
i=0
e=0
self.graph = sorted(self.graph, key=lambda item: item[2])
parent = []
rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V - 1:
u, v, weight = self.graph[i]
i += 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
e += 1
result.append([u, v, weight])
self.union(parent, rank, x, y)
print("Minimum Spanning Tree using Kruskal's Algorithm:")
print("Edge \tWeight")
for u, v, weight in result:
print(f"{u} - {v} \t {weight}")
# Example usage:
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
g.kruskal_mst()
Output:
Minimum Spanning Tree using Kruskal's Algorithm:
Edge Weight
2-3 4
0-3 5
0 - 1 10
8. Write a program to implement Quick sort for the given list of integer
values.
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
left = [x for x in arr[1:] if x <= pivot]
right = [x for x in arr[1:] if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
# Example usage:
arr = [10, 7, 8, 9, 1, 5]
print("Original array:", arr)
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)
Output:
Original array: [10, 7, 8, 9, 1, 5]
Sorted array: [1, 5, 7, 8, 9, 10]
9. Write a program to sort the elements by using heap sort.
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# Build a max heap.
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements one by one.
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
# Example usage:
arr = [12, 11, 13, 5, 6, 7]
print("Original array:", arr)
heap_sort(arr)
print("Sorted array:", arr)
Output:
Original array: [12, 11, 13, 5, 6, 7]
Sorted array: [5, 6, 7, 11, 12, 13]
10. Write a program to implement Search operation on Binary
Search Tree.
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, key):
if self.root is None:
self.root = TreeNode(key)
else:
self._insert_recursive(self.root, key)
def _insert_recursive(self, node, key):
if key < node.key:
if node.left is None:
node.left = TreeNode(key)
else:
self._insert_recursive(node.left, key)
elif key > node.key:
if node.right is None:
node.right = TreeNode(key)
else:
self._insert_recursive(node.right, key)
def search(self, key):
return self._search_recursive(self.root, key)
def _search_recursive(self, node, key):
if node is None or node.key == key:
return node
if key < node.key:
return self._search_recursive(node.left, key)
return self._search_recursive(node.right, key)
# Example usage:
bst = BinarySearchTree()
keys = [7, 4, 9, 2, 5, 8, 11]
for key in keys:
bst.insert(key)
search_key = 5
result = bst.search(search_key)
if result:
print(f"Element {search_key} found in the binary search tree.")
else:
print(f"Element {search_key} not found in the binary search tree.")
Output:
Element 5 found in the binary search tree.
