DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

Experiments
Student Name: Anurag Singh UID=22BET10338
Branch: CSE ‘IT’ Section/Group: 22BET_IOT 703/B
Semester: 5th Date of Performance: 27/08/2024
Subject Name: DAA Subject Code: 22ITH-311

1. Code for enqueue, dequeue, Isfull and Isempty operation in queues using
templates.

import java.util.Scanner;

public class Queue<T> {

private int front, rear, size, capacity;
private T[] queue;

// Constructor to initialize queue

public Queue(int capacity) {
this.capacity = capacity;
front = this.size = 0;
rear = capacity - 1;
queue = (T[]) new Object[capacity]; // Array of generic type
}

// Method to check if the queue is full

public boolean isFull() {
return (this.size == this.capacity);
}

// Method to check if the queue is empty

public boolean isEmpty() {
return (this.size == 0);
}

// Method to add an item to the queue (enqueue)

public void enqueue(T item) {
if (isFull()) {
System.out.println("Queue is full. Cannot enqueue " + item);
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
return;
}
this.rear = (this.rear + 1) % this.capacity;
this.queue[this.rear] = item;
this.size = this.size + 1;
System.out.println(item + " enqueued to queue");
}

// Method to remove an item from the queue (dequeue)

public T dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot dequeue");
return null;
}
T item = this.queue[this.front];
this.front = (this.front + 1) % this.capacity;
this.size = this.size - 1;
System.out.println(item + " dequeued from queue");
return item;
}

// Method to get the front item of the queue

public T front() {
if (isEmpty()) {
return null;
}
return this.queue[this.front];
}

// Method to get the rear item of the queue

public T rear() {
if (isEmpty()) {
return null;
}
return this.queue[this.rear];
}

// Main method for user-defined interaction with the queue

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

System.out.print("Enter the capacity of the queue: ");

DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
int capacity = scanner.nextInt();

Queue<Integer> queue = new Queue<>(capacity);

while (true) {
System.out.println("\nChoose an operation:");
System.out.println("1. Enqueue");
System.out.println("2. Dequeue");
System.out.println("3. Check if the queue is full");
System.out.println("4. Check if the queue is empty");
System.out.println("5. View the front item");
System.out.println("6. View the rear item");
System.out.println("7. Exit");
System.out.print("Enter your choice: ");
int choice = scanner.nextInt();

switch (choice) {
case 1:
System.out.print("Enter the item to enqueue: ");
int item = scanner.nextInt();
queue.enqueue(item);
break;
case 2:
queue.dequeue();
break;
case 3:
if (queue.isFull()) {
System.out.println("The queue is full.");
} else {
System.out.println("The queue is not full.");
}
break;
case 4:
if (queue.isEmpty()) {
System.out.println("The queue is empty.");
} else {
System.out.println("The queue is not empty.");
}
break;
case 5:
Integer frontItem = queue.front();
if (frontItem != null) {
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
System.out.println("Front item: " + frontItem);
} else {
System.out.println("The queue is empty.");
}
break;
case 6:
Integer rearItem = queue.rear();
if (rearItem != null) {
System.out.println("Rear item: " + rearItem);
} else {
System.out.println("The queue is empty.");
}
break;
case 7:
System.out.println("Exiting...");
scanner.close();
return;
default:
System.out.println("Invalid choice. Please try again.");
}
}
}
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Output:
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

2. Code and analyze to sort an array of integers using Merge sort

public class MergeSort {

// Method to merge two subarrays

public static void merge(int[] array, int left, int middle, int right) {
// Sizes of the subarrays
int n1 = middle - left + 1;
int n2 = right - middle;

// Temporary arrays
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];

// Copy data to temporary arrays

for (int i = 0; i < n1; ++i)
leftArray[i] = array[left + i];
for (int j = 0; j < n2; ++j)
rightArray[j] = array[middle + 1 + j];

// Initial indices of subarrays and merged array

int i = 0, j = 0;
int k = left;

// Merge the temporary arrays back into the original array

while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
array[k] = leftArray[i];
i++;
} else {
array[k] = rightArray[j];
j++;
}
k++;
}

// Copy remaining elements of leftArray, if any

while (i < n1) {
array[k] = leftArray[i];
i++;
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
k++;
}

// Copy remaining elements of rightArray, if any

while (j < n2) {
array[k] = rightArray[j];
j++;
k++;
}
}

// Method to sort an array using Merge Sort

public static void sort(int[] array, int left, int right) {
if (left < right) {
// Find the middle point
int middle = (left + right) / 2;

// Recursively sort the two halves

sort(array, left, middle);
sort(array, middle + 1, right);

// Merge the sorted halves

merge(array, left, middle, right);
}
}

// Method to print the array

public static void printArray(int[] array) {
for (int i : array) {
System.out.print(i + " ");
}
System.out.println();
}

// Main method to test the Merge Sort implementation

public static void main(String[] args) {
int[] array = {12, 11, 13, 5, 6, 7};

System.out.println("Original array:");
printArray(array);

sort(array, 0, array.length - 1);

DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

System.out.println("Sorted array:");
printArray(array);
}
}

Output:

3. Code to find the height of a Binary tree with Analysis

class Node {
int data;
Node left, right;

// Constructor to create a new node

public Node(int item) {
data = item;
left = right = null;
}
}

// Class to represent the binary tree

class BinaryTree {
Node root;

// Method to calculate the height of the binary tree

public int findHeight(Node node) {
if (node == null) {
return 0; // Base case: If the node is null, return 0 (height of an empty tree)
} else {
// Recursively calculate the height of left and right subtrees
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
int leftHeight = findHeight(node.left);
int rightHeight = findHeight(node.right);

// Height of the tree is the maximum of the heights of the left and right subtrees
plus 1
return Math.max(leftHeight, rightHeight) + 1;
}
}

// Main method to test the height calculation

public static void main(String[] args) {
BinaryTree tree = new BinaryTree();

// Creating a binary tree

tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);

// Calculating the height of the tree

int height = tree.findHeight(tree.root);
System.out.println("The height of the binary tree is: " + height);
}
}

Output:
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

4. Code to find the ignored successor in an Binary Search Trees with complexity
Analysis.

public class Binary

{

/* A binary tree node has data,

the pointer to left child
and a pointer to right child */
static class node
{
int data;
node left;
node right;
node parent;
};

static node inOrderSuccessor(

node root,
node n)
{

// step 1 of the above algorithm

if (n.right != null)
return minValue(n.right);

node succ = null;

// Start from root and search for

// successor down the tree
while (root != null)
{
if (n.data < root.data)
{
succ = root;
root = root.left;
}
else if (n.data > root.data)
root = root.right;
else
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
break;
}
return succ;
}

/* Given a non-empty binary search tree,

return the minimum data
value found in that tree. Note that
the entire tree does not need
to be searched. */
static node minValue(node node)
{
node current = node;

/* loop down to find the leftmost leaf */

while (current.left != null)
{
current = current.left;
}
return current;
}

/* Helper function that allocates a new

node with the given data and
null left and right pointers. */
static node newNode(int data)
{
node node = new node();
node.data = data;
node.left = null;
node.right = null;
node.parent = null;

return (node);
}

static node insert(node node,

int data)
{

if (node == null)
return (newNode(data));
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
else
{
node temp;
if (data <= node.data)
{
temp = insert(node.left, data);
node.left = temp;
temp.parent = node;
}
else
{
temp = insert(node.right, data);
node.right = temp;
temp.parent = node;
}
return node;
}
}

public static void main(String[] args)

{
node root = null, temp, succ, min;

// creating the tree given in the above diagram

root = insert(root, 20);
root = insert(root, 8);
root = insert(root, 22);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 10);
root = insert(root, 14);
temp = root.left.right.right;

// Function Call
succ = inOrderSuccessor(root, temp);
if (succ != null)
System.out.printf(
"\n Inorder Successor of %d is %d ",
temp.data, succ.data);
else
System.out.printf("\n Inorder Successor doesn't exit");
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
}

Output: