DATASTRUCTURESALGORITHM& ANALYSIS

LAB MANUAL
Experiment–1. Write a java program to perform various operations on single linked list
Experiment–2. Write a java program for the following a) Reverse a linked list b) Sort the data in
a linked list c) Remove duplicates d) Merge two linked lists

Experiment–3. Write a java program to perform various operations on doubly linked list
Experiment–4. Write a java program to perform various operations on circular linked

Experiment–5. Write a java program for performing various operations on stack using linked
list Experiment–6. Write a java program for performing various operations on queue Using
linked list

Experiment–7. Write a java program for the following using stack a) Infix to post fix conversion.
b) Expression evaluation. c) Obtain the binary number for a given decimal number.

Experiment–8. Write a java program to implement various operations on Binary Search Tree
Using Recursive and Non-Recursive methods.

Experiment–9. Write a java program to implement the following for a graph. a) BFS b)

DFS Experiment-10. Write a java program to implement Merge &Heap Sort of given

elements Experiment– 11. Write a java program to implement Quick Sort of given elements

Experiment– 12. Write a java program to implement various operations on AVL trees

Experiment– 13. Write a java program to perform the following operations: a) Insertion in to a
B- tree b) Searching in a B-tree

Experiment– 14. Write a java program to implementation of recursive and non- recursive
functions to Binary tree Traversals

Experiment– 15. Write a java program to implement all the functions of Dictionary (ADT) using
Hashing.

1
Exp No: Date:

JAVA PROGRAM TO PERFORM VARIOUS OPERATIONS ON SINGLE LINKED LIST

Aim:

Program:
class LinkedList
{
// Node structure
static class Node
{
int data;
Node next;
Node (int data)
{
[Link] = data;
[Link] = null;
}
}
Node head = null;

// 1. Insert at the beginning

public void insertAtHead(int data)
{ Node newNode = new
Node(data); [Link] = head;
head = newNode;
[Link]("Inserted " + data + " at head.");
}

// 2. Insert at the end

public void insertAtEnd (int data)
{
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
2
 }
Node temp = head;
while ([Link] != null)
{
temp = [Link];
}
[Link] = newNode;
[Link]("Inserted " + data + " at end.");
}

// 3. Delete a node by value

public void deleteNode(int key)
{
Node temp = head, prev = null;
// If head node itself holds the key
if (temp != null && [Link] == key)
{
head = [Link];
[Link]("Deleted " + key);
return;
}

// Search for the key to be deleted

while (temp != null && [Link] != key)
{
prev = temp;
temp = [Link];
}

// If key was not present

if (temp == null)
{
[Link]("Value " + key + " not found.");
return;
}

// Unlink the node from linked list

[Link] = [Link];
[Link]("Deleted " + key);
}

3
 // 4. Display the list
public void display()
{
if (head == null)
{
[Link]("List is empty.");
return;
}
Node temp = head;
[Link]("Linked List: ");
while (temp != null) {
[Link]([Link] + " -> ");
temp = [Link];
}
[Link]("NULL");
}

public static void main(String[] args)

{
LinkedList list = new LinkedList();
[Link](10);
[Link](20);
[Link](30);
[Link]();
[Link](10);
[Link]();
}
}

OUTPUT:

Signature of the staff

4
EXPERIMENT–2. Write a java program for the following a) Reverse a linked list b) Sort the
data in a linked list c) Remove duplicates d) Merge two linked lists
SOURCE CODE:
class LinkedList
{
static class Node
{
int data;
Node next;
Node (int data)
{
[Link] = data;
[Link] = null;
}

}
Node head = null;
// Helper to add nodes
public void add(int data)
{
Node newNode = new Node(data);
if (head == null)
{
head = newNode;
return;
}
Node temp = head;
while ([Link] != null) temp = [Link];
[Link] = newNode;

5
}
// a) Reverse a Linked List
public void reverse()
{
Node prev = null, current = head, next = null;
while (current != null)

6
 {
next = [Link]; // Store next
[Link] = prev; // Reverse pointer
prev = current; // Move prev one step
current = next; // Move current one step
}
head = prev;
}
// b) Sort the data (Bubble Sort approach)
public void sort()
{
if (head == null) return;
boolean swapped;
do {
swapped = false;
Node current = head;
while ([Link] != null)

{
if ([Link] > [Link])
{
int temp = [Link];
[Link] = [Link];
[Link] = temp;
swapped = true;
}
current = [Link];
}

7
 } while (swapped);
}
// c) Remove duplicates from a sorted list
public void removeDuplicates()
{
sort(); // Ensure list is sorted first
Node current = head;
while (current != null && [Link] != null)
{
if ([Link] == [Link])
{
[Link] = [Link];
}
else
{
current = [Link];
}
}
}
// d) Merge two linked lists
public static Node merge(Node l1, Node l2)
{
if (l1 == null) return l2;
if (l2 == null) return l1;
Node temp = l1;
while ([Link] != null) temp = [Link];
[Link] = l2;

8
 return l1;
}
public void display()
{
Node temp = head;
while (temp != null)
{

[Link]([Link] + " -> ");

temp = [Link];
}
[Link]("NULL");
}
public static void main(String[] args)
{
LinkedList list1 = new LinkedList();
[Link](30); [Link](10); [Link](20); [Link](10);
[Link]("Original List 1: "); [Link]();
[Link]();
[Link]("Reversed: "); [Link]();
[Link]();
[Link]("Sorted & Unique: "); [Link]();
LinkedList list2 = new LinkedList();
[Link](50); [Link](40);
[Link] = merge([Link], [Link]);
[Link]("Merged with List 2: "); [Link]();
}
}

9
OUTPUT:
Plaintext
Original List 1: 30 -> 10 -> 20 -> 10 -> NULL
Reversed: 10 -> 20 -> 10 -> 30 -> NULL
Sorted & Unique: 10 -> 20 -> 30 -> NULL
Merged with List 2: 10 -> 20 -> 30 -> 50 -> 40 -> NULL

EXPERIMENT–3. Write a java program to perform various operations on doubly linked list
SOURCE CODE:
class Doubly LinkedList
{
static class Node
{
int data;
Node prev;
Node next;
Node(int data)
{
[Link] = data;
[Link] = null;
[Link] = null;
}

}
Node head = null;
// 1. Insert at the Beginning
public void insertAtHead(int data)
{
Node newNode = new Node(data);
if (head != null)

1
0
 {
[Link] = newNode;
[Link] = head;
}
head = newNode;
[Link]("Inserted " + data + " at head.");
}
// 2. Insert at the End
public void insertAtEnd(int data)
{
Node newNode = new Node(data);
if (head == null)
{
head = newNode;
return;
}
Node temp = head;
while ([Link] != null)
{
temp = [Link];
}
[Link] = newNode;
[Link] = temp;
[Link]("Inserted " + data + " at end.");
}
// 3. Delete a Node
public void deleteNode(int key)

10
{
if (head == null) return;
Node temp = head;
// Search for the node to delete
while (temp != null && [Link] != key)
{
temp = [Link];
}
if (temp == null)
{
[Link]("Node with value " + key + " not found.");
return;
}
// If the node to be deleted is the head
if (temp == head)
{
head = [Link];
}
// Change next only if node to be deleted is NOT the last node
if ([Link] != null)
{
[Link] = [Link];
}
// Change prev only if node to be deleted is NOT the first node
if ([Link] != null)
{
[Link] = [Link];

11
 }
[Link]("Deleted node " + key);
}
// 4. Display Forward
public void displayForward()
{
Node temp = head;
[Link]("Forward: ");
while (temp != null) {
[Link]([Link] + " <-> ");
temp = [Link];
}
[Link]("NULL");
}
// 5. Display Backward (Shows the power of DLL)
public void displayBackward()
{

if (head == null) return;

Node temp = head;
while ([Link] != null)
{
temp = [Link];
}
[Link]("Backward: ");
while (temp != null) {
[Link]([Link] + " <-> ");
temp = [Link];

12
 }
[Link]("NULL");
}
public static void main(String[] args)
{
DoublyLinkedList dll = new DoublyLinkedList();
[Link](10);
[Link](20);
[Link](30);
[Link]();
[Link](20);
[Link]();
[Link]();
}
}
OUTPUT:Plaintext
Inserted 10 at head.
Inserted 20 at end.
Inserted 30 at end.
Forward: 10 <-> 20 <-> 30 <-> NULL
Deleted node 20
Forward: 10 <-> 30 <-> NULL
Backward: 30 <-> 10 <-> NULL

EXPERIMENT–4. Write a java program to perform various operations on circular linked

SOURCE CODE:
class Circular LinkedList
{
static class Node
{

13
 int data;
Node next;
Node(int data)
{
[Link] = data;
}
}
Node head = null;
Node tail = null;
// 1. Insert at the end
public void insert(int data)
{
Node newNode = new Node(data);
if (head == null)
{
head = newNode;
tail = newNode;
[Link] = head; // Point to itself
} else
{
[Link] = newNode;
tail = newNode;
[Link] = head; // Complete the circle
}
[Link]("Inserted: " + data);
}
// 2. Delete a node

14
public void delete(int key)
{
if (head == null) return;
Node current = head;
Node prev = null;
// Case 1: If head is the node to be deleted
if ([Link] == key)
{
if (head == tail)
{ // Only one node in list
head = null;
tail = null;
} else
{
head = [Link];
[Link] = head;
}

[Link]("Deleted head: " + key);

return;
}
// Case 2: Search for the node
do {
prev = current;
current = [Link];
} while (current != head && [Link] != key);
if ([Link] == key)
{

15
 [Link] =
[Link]; if (current
== tail)
{
tail = prev;
}
[Link]("Deleted: " + key);
} else {
[Link]("Node " + key + " not found.");
}
}
// 3. Display the list
public void display()
{
if (head == null)
{
[Link]("List is
empty."); return;
}
Node temp = head;
[Link]("Circular List: ");
do {
[Link]([Link] + " -> ");
temp = [Link];
} while (temp != head);
[Link]("(Back to Head: " + [Link] + ")");
}
public static void main(String[] args)
16
{
CircularLinkedList cll = new CircularLinkedList();
[Link](10);
[Link](20);
[Link](30);
[Link]();
[Link](20);
[Link]();
[Link](10);
[Link]();
}

}
OUTPUT:
Plaintext
Inserted: 10
Inserted: 20
Inserted: 30
Circular List: 10 -> 20 -> 30 -> (Back to Head: 10)
Deleted: 20
Circular List: 10 -> 30 -> (Back to Head: 10)
Deleted head: 10
Circular List: 30 -> (Back to Head: 30)

EXPERIMENT–5. Write a java program for performing various operations on stack using linked
list
SOURCE CODE:
class StackUsingLinkedList
{
// Node structure
static class Node
{
int data;

17
 Node next;
Node(int data)
{
[Link] = data;
[Link] = null;
}
}
private Node top = null;
// 1. Push: Add element to the top
public void push(int data)
{
Node newNode = new Node(data);
[Link] = top; // New node points to current top
top = newNode; // Top moves to the new node
[Link]("Pushed " + data + " onto stack.");
}
// 2. Pop: Remove and return the top element
public int pop()
{
if (isEmpty())
{
[Link]("Stack Underflow! Nothing to pop.");
return -1;
}
int poppedValue = [Link];
top = [Link]; // Move top to the next node
return poppedValue;
}
// 3. Peek: Return the top element without removing it
public int peek()

18
{
if (isEmpty())
{
[Link]("Stack is
empty."); return -1;
}
return [Link];
}
// 4. isEmpty: Check if stack is empty
public boolean isEmpty()
{
return top == null;
}
// 5. Display the stack
public void display()
{
if (isEmpty())
{
[Link]("Stack is
empty."); return;
}
Node temp = top;
[Link]("Stack (Top -> Bottom): ");
while (temp != null) {
[Link]([Link] + " -> ");
temp = [Link];
}
[Link]("NULL");
}
public static void main(String[] args)

19
 {
StackUsingLinkedList stack = new StackUsingLinkedList();
[Link](10);
[Link](20);
[Link](30);
[Link]();
[Link]("Top element (Peek): " + [Link]());
[Link]("Popped element: " + [Link]());
[Link]();
}
}
OUTPUT:
Plaintext
Pushed 10 onto stack.
Pushed 20 onto stack.
Pushed 30 onto stack.
Stack (Top -> Bottom): 30 -> 20 -> 10 -> NULL
Top element (Peek): 30
Popped element: 30
Stack (Top -> Bottom): 20 -> 10 -> NULL

EXPERIMENT–6. Write a java program for performing various operations on queue Using
linked list

SOURCE CODE:
class QueueUsingLinkedList
{
// Node structure
static class Node
{
int data;
Node next;
Node(int data)

20
 {
[Link] = data;
[Link] = null;
}
}
private Node front = null;
private Node rear = null;
// 1. Enqueue: Add an element to the end of the queue
public void enqueue(int data)
{
Node newNode = new Node(data);
// If queue is empty, both front and rear point to new
node if (rear == null)
{
front = rear = newNode;
[Link]("Enqueued: " + data);
return;
}
// Add the new node at the end of queue and change rear
[Link] = newNode;
rear = newNode;
[Link]("Enqueued: " + data);
}
// 2. Dequeue: Remove an element from the front of the queue
public int dequeue()
{
if (isEmpty())
{
[Link]("Queue Underflow! Nothing to remove.");
return -1;

21
 }
int value = [Link];
front = [Link]; // Move front to the next node
// If front becomes null, then change rear also to null
if (front == null)
{
rear = null;
}
return value;
}
// 3. Peek: Get the front element without removing it
public int peek()
{
if (isEmpty())
{
[Link]("Queue is
empty."); return -1;
}
return [Link];
}
// 4. isEmpty: Check if queue is empty
public boolean isEmpty()
{
return front == null;
}
// 5. Display: Print all elements in the queue
public void display()
{
if (isEmpty())
{
22
 [Link]("Queue is
empty."); return;
}
Node temp = front;
[Link]("Queue (Front -> Rear): ");
while (temp != null) {
[Link]([Link] + " -> ");
temp = [Link];
}
[Link]("NULL");
}
public static void main(String[] args)
{
QueueUsingLinkedList queue = new QueueUsingLinkedList();
[Link](10);
[Link](20);
[Link](30);
[Link]();
[Link]("Dequeued: " + [Link]());
[Link]("Front element (Peek): " + [Link]());
[Link]();
}
}
OUTPUT:
Plaintext
Enqueued: 10
Enqueued: 20
Enqueued: 30
Queue (Front -> Rear): 10 -> 20 -> 30 -> NULL
Dequeued: 10
Front element (Peek): 20
Queue (Front -> Rear): 20 -> 30 -> NULL

23
EXPERIMENT–7. Write a java program for the following using stack a) Infix to post fix
conversion. b) Expression evaluation. c) Obtain the binary number for a given decimal number.

SOURCE CODE:
import [Link];
class StackApplications
{
// Helper: Operator Precedence
static int precedence(char ch)
{
switch (ch)
{
case '+': case '-': return 1;
case '*': case '/': return 2;
case '^': return 3;
}
return -1;
}
// A) Infix to Postfix
public static String infixToPostfix(String exp)
{
StringBuilder result = new StringBuilder();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < [Link](); ++i)
{
char c = [Link](i);
if ([Link](c))
[Link](c);
else if (c == '(') [Link](c);
else if (c == ')')

24
 {
while (![Link]() && [Link]() != '(')
[Link]([Link]());
[Link]();
} else
{
while (![Link]() && precedence(c) <= precedence([Link]()))
[Link]([Link]());
[Link](c);
} }
while (![Link]()) [Link]([Link]());
return [Link]();
}
// B) Postfix Evaluation
public static int evaluatePostfix(String exp)
{
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < [Link](); i++)
{
char c = [Link](i);
if ([Link](c)) [Link](c -
'0'); else {
int val1 = [Link]();
int val2 = [Link]();
switch (c)
{
case '+': [Link](val2 + val1); break;
case '-': [Link](val2 - val1); break;
case '*': [Link](val2 * val1); break;
case '/': [Link](val2 / val1); break; } } }

25
 return [Link]();
}
// C) Decimal to Binary
public static void decimalToBinary(int n)
{
Stack<Integer> stack = new Stack<>();
int num = n;
while (n > 0)
{ [Link](n %
2); n = n / 2;
}
[Link]("Binary of " + num + ": ");
while (![Link]()) [Link]([Link]());
[Link]();
}
public static void main(String[] args)
{
String infix = "a+b*(c^d-e)";
[Link]("Infix: " + infix);
[Link]("Postfix: " +
infixToPostfix(infix)); String postfixExp = "231*+9-";
[Link]("Postfix Eval (2+3*1-9): " + evaluatePostfix(postfixExp));
decimalToBinary(13);
}
}
OUTPUT:
Plaintext
Infix: a+b*(c^d-e)
Postfix: abcd^e-*+
Postfix Eval (2+3*1-9): -4
Binary of 13: 1101

26
EXPERIMENT–8. Write a java program to implement various operations on Binary Search Tree
Using Recursive and Non-Recursive methods.

SOURCE CODE:
import [Link];
class BST
{
static class Node
{
int data;
Node left, right;
Node (int data)
{
[Link] = data;
[Link] = [Link] = null;
}
}
Node root;
// --- 1. INSERTION ---
// Recursive Insertion
public Node insertRecursive(Node root, int data)
{
if (root == null) {
return new Node(data);
}
if (data < [Link])
[Link] = insertRecursive([Link], data);
else if (data > [Link])
[Link] = insertRecursive([Link], data);
return root; }

27
 // Non-Recursive (Iterative) Insertion
public void insertIterative(int data)
{
Node newNode = new Node(data);
if (root == null)
{
root = newNode;
return;
}
Node current = root;
Node parent = null;
while (current != null)
{
parent = current;
if (data < [Link]) current = [Link];
else if (data > [Link]) current = [Link];
else return; // Duplicate
}
if (data < [Link]) [Link] = newNode;
else [Link] = newNode;
}
// --- 2. SEARCHING ---
// Recursive Search
public boolean searchRecursive(Node root, int key)
{
if (root == null) return false;
if ([Link] == key) return true;
return key < [Link] ? searchRecursive([Link], key) : searchRecursive([Link], key);
}
// Non-Recursive Search
28
 public boolean searchIterative(int key)
{
Node current = root;
while (current != null)
{
if (key == [Link]) return true;
current = (key < [Link]) ? [Link] : [Link];
}
return false;
}
// --- 3. TRAVERSAL ---
// Non-Recursive Inorder (Using Stack)
public void inorderIterative() {
if (root == null) return;
Stack<Node> stack = new Stack<>();
Node current = root;
while (current != null || ![Link]())
{ while (current != null) {
[Link](current);
current = [Link];
}
current = [Link]();
[Link]([Link] + " ");
current = [Link];
}
[Link]();
}
public static void main(String[] args)
{
BST tree = new BST();

29
 // Using iterative insert
[Link](50);
[Link](30);
[Link](70);
[Link](20);
[Link](40);
[Link]("Inorder Traversal (Iterative): ");
[Link]();
[Link]("Search 40 (Recursive): " + [Link]([Link], 40));
[Link]("Search 90 (Iterative): " + [Link](90));
}
}
OUTPUT:
Plaintext
Inorder Traversal (Iterative): 20 30 40 50 70
Search 40 (Recursive): true
Search 90 (Iterative): false

EXPERIMENT–9. Write a java program to implement the following for a graph. a) BFS b) DFS

SOURCE CODE:
import [Link].*;
class Graph {
private int V; // Number of vertices
private LinkedList<Integer> adj[]; // Adjacency List
// Constructor
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();

30
}
// Function to add an edge into the graph
void addEdge(int v, int w) {
adj[v].add(w); // Add w to v's list.
}
// a) BFS Traversal from a given source s
void BFS(int s) {
boolean visited[] = new boolean[V];
LinkedList<Integer> queue = new LinkedList<Integer>();
visited[s] = true;
[Link](s);
[Link]("BFS Traversal:
"); while ([Link]() != 0) {
s = [Link]();
[Link](s + " ");
for (int n : adj[s])
{
if (!visited[n])
{
visited[n] = true;
[Link](n);
}
}
}
[Link]();
}
// b) DFS Traversal (Recursive)
void DFSUtil(int v, boolean visited[])
{
visited[v] = true;

31
 [Link](v + " ");
for (int n : adj[v])
{
if (!visited[n])
DFSUtil(n, visited);
}
}
void DFS(int v)
{
boolean visited[] = new boolean[V];
[Link]("DFS Traversal:
"); DFSUtil(v, visited);
[Link]();
}
public static void main(String args[])
{
Graph g = new Graph(4);
[Link](0, 1);
[Link](0, 2);
[Link](1, 2);
[Link](2, 0);
[Link](2, 3);
[Link](3, 3);
[Link](2);
[Link](2);
}
}
OUTPUT:Plaintext
BFS Traversal: 2 0 3 1
DFS Traversal: 2 0 1 3

32
EXPERIMENT-10. Write a java program to implement Merge &Heap Sort of given elements

SOURCE CODE:
import [Link];
class SortingAlgorithms
{
// --- MERGE SORT ---
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
int L[] = new int[n1];
int R[] = new int[n2];
for (int i = 0; i < n1; ++i) L[i] = arr[l + i];
for (int j = 0; j < n2; ++j) R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

33
 merge(arr, l, m, r);
}
}
// --- HEAP SORT ---
public void heapSort(int arr[])
{
int n = [Link];
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Extract elements from heap one by one
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i)
{
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest =
r; if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;

34
 heapify(arr, n, largest);
}
}
public static void main(String args[])
{
SortingAlgorithms sa = new SortingAlgorithms();
int[] data1 = {12, 11, 13, 5, 6, 7};
[Link](data1, 0, [Link] - 1);
[Link]("Merge Sorted: " + [Link](data1));
int[] data2 = {4, 10, 3, 5, 1};
[Link](data2);
[Link]("Heap Sorted: " + [Link](data2));
}
}
OUTPUT:
Plaintext
Merge Sorted: [5, 6, 7, 11, 12, 13]
Heap Sorted: [1, 3, 4, 5, 10]

EXPERIMENT– 11. Write a java program to implement Quick Sort of given elements

SOURCE CODE:
import [Link];
class QuickSort
{
// This function takes the last element as pivot, places
// the pivot element at its correct position in sorted
// array, and places all smaller to left and larger to right
int partition(int arr[], int low, int high)
{
int pivot = arr[high];

35
 int i = (low - 1); // Index of smaller element
for (int j = low; j < high; j++)
{
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot)
{
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; }
// The main function that implements QuickSort
void sort(int arr[], int low, int high)
{
if (low < high)
{
// pi is partitioning index, arr[pi] is now at right place
int pi = partition(arr, low, high);

// Recursively sort elements before partition and after partition

sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}

36
 }
public static void main(String args[])
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = [Link];
QuickSort qs = new QuickSort();
[Link](arr, 0, n - 1);
[Link]("Sorted array: " + [Link](arr));
}
}
OUTPUT:
Plaintext
Sorted array: [1, 5, 7, 8, 9, 10]

EXPERIMENT– 12. Write a java program to implement various operations on AVL trees

SOURCE CODE:
class AVLTree
{
class Node
{
int key, height;
Node left, right;
Node(int d)
{
key = d;
height = 1;
}
}
Node root;
// Get height of the node

37
int height(Node N)
{
if (N == null) return 0;
return [Link];
}
// Get balance factor of node N
int getBalance(Node N)
{
if (N == null) return 0;
return height([Link]) - height([Link]);
}
// Right Rotate (used for LL Case)
Node rightRotate(Node y)
{
Node x = [Link];
Node T2 = [Link];
// Perform rotation
[Link] = y;
[Link] = T2;
// Update heights
[Link] = [Link](height([Link]), height([Link])) + 1;
[Link] = [Link](height([Link]), height([Link])) + 1;
return x;
}
// Left Rotate (used for RR Case)
Node leftRotate(Node x) {
Node y = [Link];
Node T2 = [Link];
// Perform rotation
[Link] = x;

38
 [Link] = T2;
// Update heights
[Link] = [Link](height([Link]), height([Link])) + 1;
[Link] = [Link](height([Link]), height([Link])) + 1;
return y;
}
// Recursive function to insert a key
Node insert(Node node, int key) {
// 1. Standard BST Insertion
if (node == null) return (new Node(key));
if (key < [Link])
[Link] = insert([Link], key);
else if (key > [Link])
[Link] = insert([Link], key);
else
return node; // Duplicates not allowed
// 2. Update height of this ancestor node
[Link] = 1 + [Link](height([Link]), height([Link]));
// 3. Get the balance factor
int balance = getBalance(node);
// 4. If unbalanced, try 4 cases:
// Left Left Case
if (balance > 1 && key < [Link])
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > [Link])
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > [Link])
{ [Link] = leftRotate([Link]);
39
 return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < [Link])
{ [Link] = rightRotate([Link]);
return leftRotate(node);
}
return node;
}
void preOrder(Node node)
{
if (node != null)
{
[Link]([Link] + " ");
preOrder([Link]);
preOrder([Link]);
}
}
public static void main(String[] args)
{
AVLTree tree = new AVLTree();
[Link] = [Link]([Link], 10);
[Link] = [Link]([Link], 20);
[Link] = [Link]([Link], 30); // Causes RR rotation
[Link] = [Link]([Link], 40);
[Link] = [Link]([Link], 50);
[Link] = [Link]([Link], 25); // Causes LR/RL rotation
[Link]("Preorder traversal of constructed AVL tree is:");
[Link]([Link]);
}
40
}
OUTPUT:

Plaintext
Preorder traversal of constructed AVL tree is:
30 20 10 25 40 50

EXPERIMENT– 13. Write a java program to perform the following operations: a) Insertion in
to a B-tree b) Searching in a B-tree

SOURCE CODE:
class BTree
{
private int T; // Minimum degree
public class Node
{
int n; // Current number of keys
int key[] = new int[2 * T - 1]; // Max keys
Node child[] = new Node[2 * T]; // Max children
boolean leaf;
public Node(boolean leaf)
{
[Link] = leaf;
}
}
private Node root;
public BTree(int t)
{
this.T = t;
root = new Node(true);
}

41
// --- SEARCHING ---
public Node search(Node x, int k)
{
int i = 0;
while (i < x.n && k > [Link][i])
{
i++;
}
if (i < x.n && k == [Link][i])
{
return x;
}
if ([Link])
{
return null;
}
return search([Link][i], k);
}
// --- INSERTION ---
public void insert(int k)
{
Node r = root;
if (r.n == 2 * T - 1)
{ // If root is full, tree grows in height
Node s = new Node(false);
root = s;
[Link][0] = r;
splitChild(s, 0, r);
insertNonFull(s, k);
} else
42
 {
insertNonFull(r, k);
}
}
// Split a full child node
private void splitChild(Node x, int i, Node y)
{
Node z = new Node([Link]);
z.n = T - 1;
for (int j = 0; j < T - 1; j++)
{
[Link][j] = [Link][j + T];
}
if (![Link])
{
for (int j = 0; j < T; j++)
{
[Link][j] = [Link][j + T];
}
}
y.n = T - 1;
for (int j = x.n; j >= i + 1; j--)
{
[Link][j + 1] = [Link][j];
}
[Link][i + 1] = z;
for (int j = x.n - 1; j >= i; j--)
{
[Link][j + 1] = [Link][j];
}
43
 [Link][i] = [Link][T - 1];
x.n++;
}
// Insert key into a node that is not full
private void insertNonFull(Node x, int k)
{
int i = x.n - 1;
if ([Link])
{
while (i >= 0 && k < [Link][i])
{
[Link][i + 1] = [Link][i];
i--;
}
[Link][i + 1] = k;
x.n++;
} else
{
while (i >= 0 && k < [Link][i])
{
i--;
} i++;
if ([Link][i].n == 2 * T - 1)
{
splitChild(x, i, [Link][i]);
if (k > [Link][i])
{
i++;
}
}
44
 insertNonFull([Link][i], k);
} }
public void display()
{
print(root, ""); }
private void print(Node n, String indent)
{
[Link](indent);
for (int i = 0; i < n.n; i++)
{
[Link]([Link][i] + " ");
}
[Link]();
if (![Link]) {
for (int i = 0; i <= n.n; i++)
{ print([Link][i], indent + "
");
} } }
public static void main(String[] args)
{
BTree st = new BTree(3); // Degree 3
int[] keys = {10, 20, 5, 6, 12, 30, 7, 17};
for (int k : keys) [Link](k);
[Link]("B-Tree structure:");
[Link]();
int searchKey = 12;
if ([Link]([Link], searchKey) != null) [Link]("\
nKey " + searchKey + " found in tree.");
else
[Link]("\nKey " + searchKey + " not found.");
45
} }

46
OUTPUT:
Plaintext
B-Tree structure:
10
567
12 17 20 30

Key 12 found in tree.

EXPERIMENT– 14. Write a java program to implementation of recursive and non- recursive
functions to Binary tree Traversals

SOURCE CODE:
import [Link];
class BinaryTree
{
static class Node
{
int data;
Node left, right;
Node(int data)
{
[Link] = data;
[Link] = [Link] = null;
}
}
Node root;
// --- RECURSIVE METHODS ---
void recursiveInorder(Node node)
{
if (node == null) return;
recursiveInorder([Link]);
[Link]([Link] + " ");

47
 recursiveInorder([Link]);
}
void recursivePreorder(Node node)
{
if (node == null) return;
[Link]([Link] + " ");
recursivePreorder([Link]);
recursivePreorder([Link]);
}
void recursivePostorder(Node node)
{
if (node == null) return;
recursivePostorder([Link]);
recursivePostorder([Link]);
[Link]([Link] + " ");
}
// --- NON-RECURSIVE (ITERATIVE) METHODS ---
// Preorder: Root -> Left -> Right
void iterativePreorder(Node node) {
if (node == null) return;
Stack<Node> stack = new
Stack<>(); [Link](node);
while (![Link]())
{
Node curr = [Link]();
[Link]([Link] + "
");
// Push right first so that left is processed first (LIFO)
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);

48
}

49
}
// Inorder: Left -> Root -> Right
void iterativeInorder(Node node)
{
Stack<Node> stack = new Stack<>();
Node curr = node;
while (curr != null || ![Link]())
{
while (curr != null)
{
[Link](curr);
curr = [Link];
}
curr = [Link]();
[Link]([Link] + "
"); curr = [Link];
}
}
// Postorder: Left -> Right -> Root
void iterativePostorder(Node node)
{
if (node == null) return;
Stack<Node> s1 = new Stack<>();
Stack<Node> s2 = new Stack<>();
[Link](node);
while (![Link]())
{ Node curr =
[Link]();
[Link](curr);
if ([Link] != null) [Link]([Link]);

41
0
if ([Link] != null) [Link]([Link]);

41
1
 }
while (![Link]())
{ [Link]([Link]().data + "
");
}
}

public static void main(String[] args) {

BinaryTree tree = new
BinaryTree(); [Link] = new
Node(1); [Link] = new
Node(2); [Link] = new
Node(3); [Link] = new
Node(4); [Link] = new
Node(5);
[Link]("--- Recursive Traversals ---");
[Link]("Inorder: "); [Link]([Link]); [Link]();
[Link]("Preorder: "); [Link]([Link]); [Link]();
[Link]("Postorder: "); [Link]([Link]); [Link]();
[Link]("\n--- Iterative Traversals ---");
[Link]("Inorder: "); [Link]([Link]); [Link]();
[Link]("Preorder: "); [Link]([Link]); [Link]();
[Link]("Postorder: "); [Link]([Link]); [Link]();
}
}
OUTPUT:Plaintext
--- Recursive Traversals ---
Inorder: 4 2 5 1 3
Preorder: 1 2 4 5 3
Postorder: 4 5 2 3 1

--- Iterative Traversals ---

41
2
Inorder: 4 2 5 1 3
Preorder: 1 2 4 5 3
Postorder: 4 5 2 3 1

41
3
EXPERIMENT– 15. Write a java program to implement all the functions of Dictionary (ADT)
using Hashing.

SOURCE CODE:
import [Link];
class HashDictionary
{
// A node to store the key-value pair
static class Entry
{
String key;
String value;
Entry(String key, String value)
{
[Link] = key;
[Link] = value;
}
}
private int SIZE = 10; // Number of buckets
private LinkedList<Entry>[] table;
@SuppressWarnings("unchecked")
public HashDictionary()
{
table = new LinkedList[SIZE];
for (int i = 0; i < SIZE; i++)
{
table[i] = new LinkedList<>();
}
}
// Hash Function: Generates index for a key

50
 private int getHash(String key)
{
return [Link]([Link]()) % SIZE;
}
// 1. Put Operation: Insert or Update
public void put(String key, String value)
{
int index = getHash(key);
for (Entry entry : table[index])
{
if ([Link](key))
{
[Link] = value; // Update existing key
return;
}
}
table[index].add(new Entry(key, value));
[Link]("Inserted: [" + key + " : " + value + "]");
}
// 2. Get Operation: Search
public String get(String key) {
int index = getHash(key);
for (Entry entry : table[index]) {
if ([Link](key)) {
return [Link];
}
}
return "Not Found";
}
// 3. Remove Operation: Delete

51
public void remove(String key)
{
int index = getHash(key);
Entry toRemove = null;
for (Entry entry : table[index])
{
if ([Link](key))
{
toRemove = entry;
break;
}
}
if (toRemove != null)
{
table[index].remove(toRemove);
[Link]("Removed key: " + key);
} else {
[Link]("Key not found for removal.");
}
}
// 4. Display Dictionary
public void display()
{
[Link]("\n--- Dictionary Contents ---");
for (int i = 0; i < SIZE; i++)
{
if (!table[i].isEmpty())
{
[Link]("Bucket " + i + ": ");
for (Entry entry : table[i])
52
 {
[Link]("[" + [Link] + "=" + [Link] + "] ");
}
[Link]();
}
}
}
public static void main(String[] args)
{
HashDictionary dict = new HashDictionary();
[Link]("Apple", "A red fruit");
[Link]("Ball", "A round object");
[Link]("Cat", "A small feline");
[Link]("Apple", "A sweet red fruit"); // Update test
[Link]();
[Link]("\nSearch 'Ball': " + [Link]("Ball"));
[Link]("Cat");
[Link]();
}
}
OUTPUT:Plaintext
Inserted: [Apple : A red fruit]
Inserted: [Ball : A round object]
Inserted: [Cat : A small feline]
--- Dictionary Contents ---
Bucket 0: [Cat=A small feline]
Bucket 1: [Ball=A round object]
Bucket 8: [Apple=A sweet red fruit]

Search 'Ball': A round object

Removed key: Cat
--- Dictionary Contents ---
Bucket 1: [Ball=A round object]
Bucket 8: [Apple=A sweet red fruit]

53