//1(a)

public interface List

{
public void createList(int n);
public void insertFirst(Object ob);
public void insertAfter(Object ob, Object pos);
public Object deleteFirst();
public Object deleteAfter(Object pos);
public booleanisEmpty();
public int size();
}
class ArrayList implements List
{
class Node
{ Object data;
int next;
Node(Object ob, int i) // constructor
{ data = ob;
next = i;
}
}
int MAXSIZE; // max number of nodes in the list
Node list[]; // create list array
int head, count; // count: current number of nodes in the list
ArrayList( int s) // constructor
{ MAXSIZE = s;
list = new Node[MAXSIZE];
}
public void initializeList()
{ for( int p = 0; p < MAXSIZE-1; p++ )
list[p] = new Node(null, p+1);
list[MAXSIZE-1] = new Node(null, -1);
}
public void createList(int n) // create ‘n’ nodes
{ int p;
for( p = 0; p < n; p++ )
{
list[p] = new Node(11+11*p, p+1);
count++;
}
list[p-1].next = -1; // end of the list
}
public void insertFirst(Object item)
{
if( count == MAXSIZE )
{ [Link]("***List is FULL");
return;
}
int p = getNode();
if( p != -1 )
{
list[p].data = item;
if( isEmpty() ) list[p].next = -1;
else list[p].next = head;
head = p;
count++;
}
}
public void insertAfter(Object item, Object x)
{
if( count == MAXSIZE )
{ [Link]("***List is FULL");
return;}
int q = getNode(); // get the available position to insert new node
int p = find(x); // get the index (position) of the Object x
if( q != -1 )
{ list[q].data = item;
list[q].next = list[p].next;
list[p].next = q;
count++;}
}
public int getNode() // returns available node index
{ for( int p = 0; p < MAXSIZE; p++ )
if(list[p].data == null) return p;
return -1;
}
public int find(Object ob) // find the index (position) of the Object ob
{ int p = head;
while( p != -1)
{ if( list[p].data == ob ) return p;
p = list[p].next; // advance to next node
}
return -1;
}
public Object deleteFirst()
{ if( isEmpty() )
{ [Link]("List is empty: no deletion");
return null;
}
Object tmp = list[head].data;
if( list[head].next == -1 ) // if the list contains one node,
head = -1; // make list empty.
else
head = list[head].next;
count--; // update count
return tmp;
}
public Object deleteAfter(Object x)
{ int p = find(x);
if( p == -1 || list[p].next == -1 )
{ [Link]("No deletion");
return null;
}
int q = list[p].next;
Object tmp = list[q].data;
list[p].next = list[q].next;
count--;
return tmp;
}
public void display()
{ int p = head;
[Link]("\nList: [ " );
while( p != -1)
{ [Link](list[p].data + " "); // print data
p = list[p].next; // advance to next node
}
[Link]("]\n");//
}
public booleanisEmpty()
{ if(count == 0) return true;
else return false;
}
public int size()
{ return count; }
}

class ArrayListDemo
{
public static void main(String[] args)
{
ArrayListlinkedList = new ArrayList(10);
[Link]();
[Link](4); // create 4 nodes
[Link](); // print the list
[Link]("InsertFirst 55:");
[Link](55);
[Link]();
[Link]("Insert 66 after 33:");
[Link](66, 33); // insert 66 after 33
[Link]();
Object item = [Link](); [Link]("Deleted node: " + item);
[Link]();
[Link]("InsertFirst 77:");
[Link](77);
[Link]();
item = [Link](22); // delete node after node 22
[Link]("Deleted node: " + item);
[Link]();
[Link]("size(): " + [Link]());
}
}
Output:
E:\javac [Link]
E:\java ArrayListDemo
List: [ 11 22 33 44 ]
InsertFirst 55:
List: [ 55 11 22 33 44 ]
Insert 66 after 33:
List: [ 55 11 22 33 66 44 ]
Deleted node: 55
List: [ 11 22 33 66 44 ]
InsertFirst 77:
List: [ 77 11 22 33 66 44 ]
Deleted node: 33
List: [ 77 11 22 66 44 ]
size(): 5
1(b)
class LinkedList implements List
{
class Node
{ Object data; // data item
Node next; // refers to next node in the list
Node( Object d ) // constructor
{ data = d; } // ‘next’ is automatically set to null
}
Node head; // head refers to first node
Node p; // p refers to current node
int count; // current number of nodes
public void createList(int n) // create 'n' nodes
{
p = new Node(11); // create first node
head = p; // assign mem. address of 'p' to 'head'
for( inti = 1; i< n; i++ ) // create 'n-1' nodes
p = [Link] = new Node(11 + 11*i);
count = n;
}
public void insertFirst(Object item) // insert at the beginning of list
{
p = new Node(item); // create new node
[Link] = head; // new node refers to old head
head = p; // new head refers to new node
count++;
}
public void insertAfter(Object item,Object key)
{
p = find(key); // get “location of key item”
if( p == null )
[Link](key + " key is not found");
else
{ Node q = new Node(item); // create new node
[Link] = [Link]; // new node next refers to [Link]
[Link] = q; // [Link] refers to new node
count++;
}
}
public Node find(Object key)
{
p = head;
while( p != null ) // start at beginning of list until end of list
{
if( [Link] == key ) return p; // if found, return key address
p = [Link]; // move to next node
}
return null; // if key search is unsuccessful, return null
}
public Object deleteFirst() // delete first node
{
if( isEmpty() )
{ [Link]("List is empty: no deletion");
return null;
}
Node tmp = head; // tmp saves reference to head
head = [Link];
count--;
return [Link];
}
public Object deleteAfter(Object key) // delete node after key item
{ p = find(key); // p = “location of key node”
if( p == null )
{ [Link](key + " key is not found");
return null;
}
if( [Link] == null ) // if(there is no node after key node)
{ [Link]("No deletion");
return null;
}
else
{ Nodetmp = [Link]; // save node after key node
[Link] = [Link]; // point to next of node deleted
count--;
return [Link]; // return deleted node
}
}
public void displayList()
{ p = head; // assign mem. address of 'head' to 'p'
[Link]("\nLinked List: ");
while( p != null ) // start at beginning of list until end of list
{ [Link]([Link] + " -> "); // print data
p = [Link]; // move to next node
}
[Link](p); // prints 'null'
}
public booleanisEmpty() // true if list is empty
{ return (head == null); }
public int size()
{ return count; }
} // end of LinkeList class
class LinkedListDemo
{ public static void main(String[] args)
{ LinkedList list = new LinkedList(); // create list object
[Link](4); // create 4 nodes
[Link]();
[Link](55); // insert 55 as first node
[Link]();
[Link](66, 33); // insert 66 after 33
[Link]();
Object item = [Link](); // delete first node
if( item != null )
{ [Link]("deleteFirst(): " + item);
[Link]();
}
item = [Link](22); // delete a node after node(22)
if( item != null )
{ [Link]("deleteAfter(22): " + item);
[Link]();
}
[Link]("size(): " + [Link]());
}
}
Output:

E:\javac [Link]

E:\java LinkedListDemo

Linked List: 11 -> 22 -> 33 -> 44 -> null

Linked List: 55 -> 11 -> 22 -> 33 -> 44 -> null

Linked List: 55 -> 11 -> 22 -> 33 -> 66 -> 44 -> null

deleteFirst(): 55

Linked List: 11 -> 22 -> 33 -> 66 -> 44 -> null

deleteAfter(22): 33

Linked List: 11 -> 22 -> 66 -> 44 -> null

size(): 4
//2(a)
public interface Stack
{
public void push(Object ob);
public Object pop();
public Object peek();
public boolean isEmpty();
public int size();
}

public class ArrayStack implements Stack

{
private Object a[];
private int top; // stack top
public ArrayStack(int n) // constructor
{ a = new Object[n]; // create stack array
top = -1; // no items in the stack
}
public void push(Object item) // add an item on top of stack
{
if(top == [Link]-1)
{ [Link]("Stack is full");
return;
}
top++; // increment top
a[top] = item; // insert an item
}
public Object pop() // remove an item from top of stack
{
if( isEmpty() )
{ [Link]("Stack is empty");
return null;
}
Object item = a[top]; // access top item
top--; // decrement top
return item;
}
public Object peek() // get top item of stack
{ if( isEmpty() ) return null;
return a[top];
}
public boolean isEmpty() // true if stack is empty
{ return (top == -1); }
public int size() // returns number of items in the stack
{ return top+1; }
}

class ArrayStackDemo
{
public static void main(String[] args)
{
ArrayStack stk = new ArrayStack(4); // create stack of size 4
Object item;
[Link]('A'); // push 3 items onto stack
[Link]('B');
[Link]('C');
[Link]("size(): "+ [Link]());
item = [Link](); // delete item
[Link](item + " is deleted");
[Link]('D'); // add three more items to the stack
[Link]('E');
[Link]('F');
[Link]([Link]() + " is deleted");
[Link]('G'); // push one item
item = [Link](); // get top item from the stack
[Link](item + " is on top of stack");
}
}
Output :

E:\javac [Link]

E:\javac [Link]

E:\java ArrayStackDemo
size(): 3

C is deleted

Stack is full

E is deleted

G is on top of stack
2(b)
Public interface Queue
{
public void insert(Object ob);
public Object remove();
public Object peek();
public booleanisEmpty();
public int size();
}
class ArrayQueue implements Queue
{ private int maxSize; // maximum queue size
private Object[] que; // que is an array
private int front;
private int rear;
private int count; // count of items in queue (queue size)
public ArrayQueue(int s) // constructor
{ maxSize = s;
que = new Object[maxSize];
front = rear = -1;
count = 0;
}
public void insert(Object item) // add item at rear of queue
{
if( count == maxSize )
{ [Link]("Queue is Full"); return; }
if(rear == maxSize-1 || rear == -1)
{ que[0] = item;
rear = 0;
if( front == -1) front = 0;
}
else que[++rear] = item;
count++; // update queue size
}
public Object remove() // delete item from front of queue
{
if( isEmpty() )
{[Link]("Queue is Empty"); return 0; }
Object tmp = que[front]; // save item to be deleted
que[front] = null; // make deleted item’s cell empty
if( front == rear )
rear = front = -1;
else if( front == maxSize-1 ) front = 0;
else front++;
count--; // less one item from the queue size
return tmp;
}
public Object peek() // peek at front of the queue
{ return que[front]; }
public booleanisEmpty() // true if the queue is empty
{ return (count == 0); }
public int size() // current number of items in the queue
{ return count; }
public void displayAll()
{
[Link]("Queue: ");
for( inti = 0; i<maxSize; i++ )
[Link]( que[i] + " ");
[Link]();
}
}
class QueueDemo
{
public static void main(String[] args)
{
/* queue holds a max of 5 items */
ArrayQueue q = new ArrayQueue(5);
Object item;
[Link]('A'); [Link]('B'); [Link]('C'); [Link]();
item = [Link](); // delete item
[Link](item + " is deleted");
item = [Link]();
[Link](item + " is deleted");
[Link]();
[Link]('D'); // insert 3 more items
[Link]('E');
[Link]('F');
[Link]();
item = [Link]();
[Link](item + " is deleted");
[Link]();
[Link]("peek(): " + [Link]());
[Link]('G');
[Link]();
[Link]("Queue size: " + [Link]());
}
}
Output:

E:\javac [Link]

E:\javac [Link]

E:\java QueueDemo
Queue: A B C null null
A is deleted
B is deleted
Queue: null null C null null
Queue: F null C D E
C is deleted
Queue: F null null D E
peek(): D
Queue: F G null D E
Queue size: 4
Program 3(a):Infix to postfix conversion

import [Link];
class InfixToPostfix
{
[Link]<Character>stk =
new [Link]<Character>();
public String toPostfix(String infix)
{
infix = "(" + infix + ")"; // enclose infix expr within parentheses
String postfix = "";
/* scan the infix char-by-char until end of string is reached */
for( inti=0; i<[Link](); i++)
{
char ch, item;
ch = [Link](i);
if( isOperand(ch) ) // if(ch is an operand), then
postfix = postfix + ch; // append ch to postfix string

if( ch == '(' ) // if(ch is a left-bracket), then

[Link](ch); // push onto the stack
if( isOperator(ch) ) // if(ch is an operator), then
{
item = [Link](); // pop an item from the stack
/* if(item is an operator), then check the precedence of ch and item*/
if( isOperator(item) )
{
if( precedence(item) >= precedence(ch) )
{
[Link](item);
[Link](ch);
}
else
{ postfix = postfix + item;
[Link](ch);
}
}
else
{ [Link](item);
[Link](ch);
}
} // end of if(isOperator(ch))
if( ch == ')' )
{
item = [Link]();
while( item != '(' )
{
postfix = postfix + item;
item = [Link]();
}
}
} // end of for-loop
return postfix;
} // end of toPostfix() method
public booleanisOperand(char c)
{ return(c >= 'A' && c <= 'Z'); }
public booleanisOperator(char c)
{
return( c=='+' || c=='-' || c=='*' || c=='/' );
}
public int precedence(char c)
{
int rank = 1; // rank = 1 for '*’ or '/'
if( c == '+' || c == '-' ) rank = 2;
return rank;
}
}

class InfixToPostfixDemo
{
public static void main(String args[])
{

InfixToPostfix obj = new InfixToPostfix();

Scanner in = new Scanner([Link]);
[Link]("Enter the Infix Expression: ");
//reading the number of elements from the that we want to enter
String name = [Link]();
[Link]("infix: " + name );
[Link]("postfix:"+[Link](name) );
}
}
Output:
E:\>javac [Link]
E:\>java InfixToPostfixDemo
Enter the Infix Expression: A*(B+C/D)-E
infix: A*(B+C/D)-E
postfix:ABCD/+*E-
//program 3(b):Evaluate Postfix Expression
import [Link];
class EvaluatePostfixExpression
{
public static void main(String args[])
{
Scanner in = new Scanner([Link]);
[Link]("Enter the postfix Expression: ");
String postfix = [Link]();
[Link]<Integer>stk =new [Link]<Integer>();
char ch;
for( inti = 0; i<[Link](); i++ )
{
ch = [Link](i);
if( isDigit(ch) )
[Link]( new Integer([Link](ch,10)));
if( isOperator(ch) )
{
int tmp1 = [Link]();
int tmp2 = [Link]();
int result = evaluate(tmp2, tmp1, ch);
[Link](result);
}
}
[Link]("Value of postfix expr = " + [Link]());
}
static booleanisDigit(char c)
{ return( c >= '0' && c <= '9' ); }
static booleanisOperator(char c)
{ return( c=='+' || c=='-' || c=='*' || c=='/' ); }
static int evaluate(int a, int b, char op)
{ int res = 0;
switch(op)
{
case '+' : res = (a+b); break;
case '-' : res = (a-b); break;
case '*' : res = (a*b); break;
case '/' : res = (a/b); break;
}
return res;
}
}
Output:

E:\>javac [Link]

E:\>java EvaluatePostfixExpression

Enter the postfix Expression: 5 6 2 + * 8 4 / -

Value of postfix expr = 38

// [Link] queue
class Node
{ String data; // data item
int prn; // priority number (minimum has highest priority)
Node next; // "next" refers to the next node
Node( String str, int p ) // constructor
{ data = str;
prn = p; } // "next" is automatically set to null
}
class LinkedPriorityQueue
{
Node head; // “head” refers to first node
public void insert(String item, int pkey) // insert item after pkey
{
Node newNode = new Node(item, pkey); // create new node
int k;
if( head == null ) k = 1;
else if( [Link]<[Link] ) k = 2;
else k = 3;
switch( k )
{ case 1: head = newNode; // Q is empty, add head node
[Link] = null;
break;
case 2: Node oldHead = head; // add one item before head
head = newNode;
[Link] = oldHead;
break;
case 3: Node p = head; // add item before a node
Node prev = p;
Node nodeBefore = null;
while( p != null )
{
if( [Link]<[Link] )
{ nodeBefore = p;
break;
}
else
{ prev = p; // save previous node of current node
p = [Link]; // move to next node
} } // end of while
[Link] = nodeBefore;
[Link] = newNode;
} // end of switch
} // end of insert() method
public Node delete()
{
if( isEmpty() )
{ [Link]("Queue is empty");
return null;}
else
{ Nodetmp = head;
head = [Link];
return tmp; }
}
public void displayList()
{
Node p = head; // assign address of head to p
[Link]("\nQueue: ");
while( p != null ) // start at beginning of list until end of list
{
[Link]([Link]+"(" +[Link]+ ")" + " ");
p = [Link]; // move to next node
}
[Link](); }
public booleanisEmpty() // true if list is empty
{ return (head == null); }
public Node peek() // get first item
{ return head; }
}
class LinkedPriorityQueueDemo
{
public static void main(String[] args)
{
LinkedPriorityQueuepq = new LinkedPriorityQueue(); // create new queue list
Node item;
[Link]("Babu", 3);
[Link]("Nitin", 2);
[Link]("Laxmi", 2);
[Link]("Kim", 1);
[Link]("Jimmy", 3);
[Link]();
item = [Link]();
if( item != null )
[Link]("delete():" + [Link]+ "(" +[Link]+")");
[Link]();
[Link]("Scot", 2);
[Link]("Anu", 1);
[Link]("Lehar", 4);
[Link](); } }
Output:

E:\javac [Link]

E:\java LinkedPriorityQueueDemo

Queue: Kim(1) Nitin(2) Laxmi(2) Babu(3) Jimmy(3)

delete():Kim(1)

Queue: Nitin(2) Laxmi(2) Babu(3) Jimmy(3)

Queue: Anu(1) Nitin(2) Laxmi(2) Scot(2) Babu(3) Jimmy(3) Lehar(4)

//Program 5(a): Insertion an element into binary search tree
import [Link].*;
import [Link];
// A class to store a BST node
class Node
{
int data;
Node left = null, right = null;
Node(int data) {
[Link] = data;
}
}

class BST
{
// Function to perform inorder traversal on the tree
public static void inorder(Node root)
{
if (root == null) {
return;
}
inorder([Link]);
[Link]([Link] + " ");
inorder([Link]);
}
// Function to construct balanced BST from the given sorted array
public static Node convert(int[] keys, int low, int high, Node root)
{
// base case
if (low > high) {
return root;
}
// find the middle element of the current range
int mid = (low + high) / 2;
// construct a new node from the middle element and assign it to the root
root = new Node(keys[mid]);
// left subtree of the root will be formed by keys less than middle element
[Link] = convert(keys, low, mid - 1, [Link]);
// right subtree of the root will be formed by keys more than the
 // middle element
[Link] = convert(keys, mid + 1, high, [Link]);
return root;
}
// Function to construct balanced BST from the given unsorted array
public static Node convert(int[] keys)
{
// sort the keys first
[Link](keys);
// construct a balanced BST and return the root node of the tree
return convert(keys, 0, [Link] - 1, null);
}
public static void main(String[] args)
{
// input keys
int[] keys = { 15, 10, 20, 8, 12, 16, 25 };
// construct a balanced binary search tree
Node root = convert(keys);
// print the keys in an inorder fashion
inorder(root);
}
}
Output:

E:\>javac [Link]

E:\>java BST

8 10 12 15 16 20 25
//Program 5(b):Delete an element from a binary search tree
class Node
{
int data;
Node left = null, right = null;
Node(int data) {
[Link] = data;
}
}

class BSTDel
{
// Function to perform inorder traversal on the BST
public static void inorder(Node root)
{
if (root == null) {
return;
}
inorder([Link]);
[Link]([Link] + " ");
inorder([Link]);
}
// Helper function to find minimum value node in the subtree rooted at `curr`
public static Node getMinimumKey(Node curr)
{
while ([Link] != null) {
curr = [Link];
}
return curr;
}
// Recursive function to insert a key into a BST
public static Node insert(Node root, int key)
{
// if the root is null, create a new node and return it
if (root == null) {
return new Node(key);
}
// if the given key is less than the root node, recur for the left subtree
if (key <[Link]) {
[Link] = insert([Link], key);
 }
// if the given key is more than the root node, recur for the right subtree
else {
[Link] = insert([Link], key);
}
return root;
}
// Function to delete a node from a BST
public static Node deleteNode(Node root, int key)
{
// pointer to store the parent of the current node
Node parent = null;
// start with the root node
Node curr = root;

// search key in the BST and set its parent pointer

while (curr != null &&[Link] != key)
{
// update the parent to the current node
parent = curr;
// if the given key is less than the current node, go to the left subtree;
// otherwise, go to the right subtree
if (key <[Link]) {
curr = [Link];
}
else {
curr = [Link];
}
}
// return if the key is not found in the tree
if (curr == null) {
return root;
}
// Case 1: node to be deleted has no children, i.e., it is a leaf node
if ([Link] == null &&[Link] == null)
{
// if the node to be deleted is not a root node, then set its
// parent left/right child to null
if (curr != root)
{
 if ([Link] == curr) {
[Link] = null;
}
else {
[Link] = null;
}
}
// if the tree has only a root node, set it to null
else {
root = null;
}
}
// Case 2: node to be deleted has two children
else if ([Link] != null &&[Link] != null)
{
// find its inorder successor node
Node successor = getMinimumKey([Link]);
// store successor value
int val = [Link];
// recursively delete the successor. Note that the successor
// will have at most one child (right child)
deleteNode(root, [Link]);
// copy value of the successor to the current node
[Link] = val;
}
// Case 3: node to be deleted has only onechild
else {
// choose a child node
Node child = ([Link] != null)? [Link]: [Link];
// if the node to be deleted is not a root node, set its parent
// to its child
if (curr != root)
{
if (curr == [Link]) {
[Link] = child;
}
else {
[Link] = child;
}
}
 // if the node to be deleted is a root node, then set the root to the child
else {
root = child;
}
}
return root;
}

public static void main(String[] args)

{
int[] keys = { 15, 10, 20, 8, 12, 16 };
Node root = null;
for (int key: keys) {
root = insert(root, key);
}

root = deleteNode(root, 16);

inorder(root);
}
}
Output:

E:\>javac [Link]

E:\>java BSTDel

8 10 12 15 20
Program 5(c):Search for a key element in a binary search
class Node
{
int data;
Node left = null, right = null;
Node(int data) {
[Link] = data;
}
}
class BSTsearch
{
// Recursive function to insert a key into a BST
public static Node insert(Node root, int key)
{
// if the root is null, create a new node and return it
if (root == null) {
return new Node(key);
}
// if the given key is less than the root node, recur for the left subtree
if (key <[Link]) {
[Link] = insert([Link], key);
}
// if the given key is more than the root node, recur for the right subtree
else {
[Link] = insert([Link], key);
}
return root;
}
// Recursive function to search in a given BST
public static void search(Node root, int key, Node parent)
{
// if the key is not present in the key
if (root == null)
{
[Link]("Key Not found");
return;
}
// if the key is found
if ([Link] == key)
{
 if (parent == null) {
[Link]("The node with key " + key + " is root node");
}
else if (key <[Link])
{
[Link]("The given key is the left node of the node " +
"with key " + [Link]);
}
else {
[Link]("The given key is the right node of the node " +
"with key " + [Link]);
}
return;
}
// if the given key is less than the root node, recur for the left subtree;
// otherwise, recur for the right subtree
if (key <[Link]) {
search([Link], key, root);
}
else {
search([Link], key, root);
}
}
public static void main(String[] args)
{
int[] keys = { 15, 10, 20, 8, 12, 16, 25 };
Node root = null;
for (int key: keys) {
root = insert(root, key);
}
search(root, 25, null);
}
}
Output:

E:\>javac [Link]

E:\>java BSTsearch

The given key is the right node of the node with key 20
Program 6:AVL tree-Insertion and Deletion
// Create node
class Node {
int item, height;
Node left, right;
Node(int d) {
item = d;
height = 1;
}
}
// Tree class
class AVLTree {
Node root;
int height(Node N) {
if (N == null)
return 0;
return [Link];
}
int max(int a, int b) {
return (a > b) ? a : b;
}
Node rightRotate(Node y) {
Node x = [Link];
Node T2 = [Link];
[Link] = y;
[Link] = T2;
[Link] = max(height([Link]), height([Link])) + 1;
[Link] = max(height([Link]), height([Link])) + 1;
return x;
}
Node leftRotate(Node x) {
Node y = [Link];
Node T2 = [Link];
[Link] = x;
[Link] = T2;
[Link] = max(height([Link]), height([Link])) + 1;
[Link] = max(height([Link]), height([Link])) + 1;
return y;
 }
// Get balance factor of a node
int getBalanceFactor(Node N) {
if (N == null)
return 0;
return height([Link]) - height([Link]);
}
// Insert a node
Node insertNode(Node node, int item) {
// Find the position and insert the node
if (node == null)
return (new Node(item));
if (item <[Link])
[Link] = insertNode([Link], item);
else if (item >[Link])
[Link] = insertNode([Link], item);
else
return node;
// Update the balance factor of each node
// And, balance the tree
[Link] = 1 + max(height([Link]), height([Link]));
int balanceFactor = getBalanceFactor(node);
if (balanceFactor> 1) {
if (item <[Link]) {
return rightRotate(node);
} else if (item >[Link]) {
[Link] = leftRotate([Link]);
return rightRotate(node);
}
}
if (balanceFactor< -1) {
if (item >[Link]) {
return leftRotate(node);
} else if (item <[Link]) {
[Link] = rightRotate([Link]);
return leftRotate(node);
}
}
return node;
}
Node nodeWithMimumValue(Node node) {
Node current = node;
while ([Link] != null)
current = [Link];
return current;
}
// Delete a node
Node deleteNode(Node root, int item) {
// Find the node to be deleted and remove it
if (root == null)
return root;
if (item <[Link])
[Link] = deleteNode([Link], item);
else if (item >[Link])
[Link] = deleteNode([Link], item);
else {
if (([Link] == null) || ([Link] == null)) {
Node temp = null;
if (temp == [Link])
temp = [Link];
else
temp = [Link];
if (temp == null) {
temp = root;
root = null;
} else
root = temp;
} else {
Node temp = nodeWithMimumValue([Link]);
[Link] = [Link];
[Link] = deleteNode([Link], [Link]);
}
}
if (root == null)
return root;
// Update the balance factor of each node and balance the tree
[Link] = max(height([Link]), height([Link])) + 1;
int balanceFactor = getBalanceFactor(root);
if (balanceFactor> 1) {
if (getBalanceFactor([Link]) >= 0) {
 return rightRotate(root);
} else {
[Link] = leftRotate([Link]);
return rightRotate(root);
}
}
if (balanceFactor< -1) {
if (getBalanceFactor([Link]) <= 0) {
return leftRotate(root);
} else {
[Link] = rightRotate([Link]);
return leftRotate(root);
}
}
return root;
}

void preOrder(Node node) {

if (node != null) {
[Link]([Link] + " ");
preOrder([Link]);
preOrder([Link]);
}
}
// Print the tree
private void printTree(Node currPtr, String indent, boolean last) {
if (currPtr != null) {
[Link](indent);
if (last) {
[Link]("R----");
indent += " ";
} else {
[Link]("L----");
indent += "| ";
}
[Link]([Link]);
printTree([Link], indent, false);
printTree([Link], indent, true);
}
}
 // Driver code
public static void main(String[] args) {
AVLTree tree = new AVLTree();
[Link] = [Link]([Link], 33);
[Link] = [Link]([Link], 13);
[Link] = [Link]([Link], 53);
[Link] = [Link]([Link], 9);
[Link] = [Link]([Link], 21);
[Link] = [Link]([Link], 61);
[Link] = [Link]([Link], 8);
[Link] = [Link]([Link], 11);
[Link]([Link], "", true);
[Link] = [Link]([Link], 13);
[Link]("After Deletion: ");
[Link]([Link], "", true);
}
}
Output:

E:\>javac [Link]

E:\>java AVLTree

R----33

L----13

| L----9

| | L----8

| | R----11

| R----21

R----53

R----61

After Deletion:

R----33

L----9

| L----8

| R----21

| L----11

R----53

R----61
//Breadth First Search for a given graph
class Node
{ int label; // vertex label
Node next; // next node in list
Node( int b ) // constructor
{ label = b; }
}
class Graph
{ int size;
Node adjList[];
int mark[];
Graph(int n) // constructor
{ size = n;
adjList = new Node[size];
mark = new int[size];
}
public void createAdjList(int a[][]) // create adjacent lists
{ Node p; int i, k;
for( i = 0; i< size; i++ )
{ p = adjList[i] = new Node(i);
for( k = 0; k < size; k++ )
{ if( a[i][k] == 1 )
{ [Link] = new Node(k);
p = [Link];
}
} // end of inner for-loop
} // end of outer for-loop
} // end of createAdjList()
public void bfs(int head)
{ int v; Node adj;
Queue q = new Queue(size);
v = head;
mark[v] = 1;
[Link](v + " ");
[Link](v);
while( ![Link]() ) // while(queue not empty)
{
v = [Link]();
adj = adjList[v];
while( adj != null )
{ v = [Link];
if( mark[v] == 0 )
{ [Link](v);
mark[v] = 1;
[Link](v + " ");
}
adj = [Link];
}
}
}
} // end of Graph class
class Queue
{ private int maxSize; // max queue size
private int[] que; // que is an array of integers
private int front;
private int rear;
private int count; // count of items in queue
public Queue(int s) // constructor
{ maxSize = s;
que = new int[maxSize];
front = rear = -1;
}
public void qinsert(int item)
{ if( rear == maxSize-1 )
[Link]("Queue is Full");
else { rear = rear + 1;
que[rear] = item;
if( front == -1 ) front = 0;
}
}
public int qdelete()
{ int item;
if( IsEmpty() )
{ [Link]("\n Queue is Empty");
return(-1);
}
item = que[front];
if( front == rear ) front = rear = -1;
else front = front+1;
return(item);
}
public booleanIsEmpty()
{ return( front == -1 ); }
} // end of Queue class
class BfsDemo
{ public static void main(String[] args)
{ Graph g = new Graph(5);
int a[][] = { {0,1,0,1,1}, {1,0,1,1,0}, {0,1,0,1,1},
{1,1,1,0,0}, {1,0,1,0,0}};
[Link](a);
[Link](0);
}
}
Output:

E:\>javac [Link]

E:\>java BfsDemo

01342
//DFS
class Node
{ int label; // vertex label
Node next; // next node in list
Node( int b ) // constructor
{ label = b; }
}
class Graph
{ int size;
Node adjList[];
int mark[];
Graph(int n) // constructor
{ size = n;
adjList = new Node[size];
mark = new int[size]; // elements of mark are initialized to 0
}
public void createAdjList(int a[][]) // create adjacent lists
{
Node p; int i, k;
for( i = 0; i< size; i++ )
{ p = adjList[i] = new Node(i); //create first node of ith adj. list
for( k = 0; k < size; k++ )
{ if( a[i][k] == 1 )
{ [Link] = new Node(k); // create next node of ith adj. list
p = [Link];
}
}
}
}
public void dfs(int head) // recursive depth-first search
{ Node w; int v;
mark[head] = 1;
[Link]( head + " ");
w = adjList[head];
while( w != null)
{ v = [Link];
if( mark[v] == 0 ) dfs(v);
w = [Link];
}
}
}
class DfsDemo
{
public static void main(String[] args)
{
Graph g = new Graph(5); // graph is created with 5 nodes
int a[][] = { {0,1,0,1,1}, {1,0,1,1,0}, {0,1,0,1,1},
{1,1,1,0,0}, {1,0,1,0,0}};
[Link](a);
[Link](0); // starting node to dfs is0 (i.e., A)
}
}
Output:

E:\javac [Link]

E:\java DfsDemo

01234
//9(a)Linear Search

class LinearSearchDemo

static Object[] a = { 89, 45, 175, 7, 50, 43, 126, 90 };

static Object key = 126;

public static void main(String args[])

if( linearSearch() )

[Link](key + " found in the list");

else

[Link](key + " not found in the list");

static booleanlinearSearch()

for( inti=0; i<[Link]; i++)

if(key == a[i]) return true;

return false;

}
E:\javac [Link]

E:\java LinearSearchDemo

126 found in the list

//9(b) Binary search
class BinarySearchDemo
{
static Object[] a = { "AP", "KA", "MH", "MP", "OR", "TN", "UP", "WB"};
static Object key = "UP";
public static void main(String args[])
{
if( binarySearch() )
[Link](key + " found in the list");
else
[Link](key + " not found in the list");
}
static booleanbinarySearch()
{
int c, mid, low = 0, high = [Link]-1;
while( low<= high)
{
mid = (low + high)/2;
c = ((Comparable)key).compareTo(a[mid]);

if( c< 0) high = mid-1;

else if( c> 0) low = mid+1;
else return true;
}
return false;
}
}
Output:
E:\javac [Link]

E:\java BinarySearchDemo

UP found in the list

//program 10(a):Bubblesort

import [Link];
public class BubbleSortDemo
{
static void bubbleSort(int[] arr) {
int n = [Link];
int temp = 0;
for(int i=0; i< n; i++){
for(int j=1; j < (n-i); j++){
if(arr[j-1] >arr[j]){
//swap elements
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;}
}
}
}
public static void main(String[] args)
{
int n;
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of elements : ");
n=[Link]();
int[] arr = new int[n];
[Link]("Enter the elements of the array: ");
for(int i=0; i<n; i++)
//reading array elements from the user
arr[i]=[Link]();
[Link]("Array Before Bubble Sort");
for(int i=0; i<[Link]; i++)
{
[Link](arr[i] + " ");
}
[Link]();
bubbleSort(arr);
[Link]("Array After Bubble Sort");
for(int i=0; i<[Link]; i++)
[Link](arr[i] + " ");
}
}

Output:

E:\>javac [Link]

E:\>java BubbleSortDemo

Enter the number of elements : 6

Enter the elements of the array:

54

67

14

25

87

29

Array Before Bubble Sort

54 67 14 25 87 29

Array After Bubble Sort

14 25 29 54 67 87
//Program 10(b):Selection Sort
import [Link];
class SelectionSortDemo
{
public static void main(String[] args)
{
int n;
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of elements : ");
n=[Link]();
int[] arr = new int[n];
[Link]("Enter the elements of the array: ");
for(int i=0; i<n; i++)
{
//reading array elements from the user
arr[i]=[Link](); }
[Link]("\n Unsorted array: ");
display( arr );
selectionSort( arr );
[Link]("\n Sorted array: ");
display( arr ); }
static void selectionSort( intarr[] )
{
int n = [Link];
for( int pass = 0; pass < n-1; pass++ )
{
int min = pass;
for( inti = pass+1; i< n; i++ )
if( arr[i] <arr[min] ) min = i;
if( min != pass )
{
int tmp = arr[min];
arr[min] = arr[pass];
arr[pass] = tmp; } } }
static void display( intarr[] )
{
for( inti = 0; i<[Link]; i++ )
[Link]( arr[i] + " " ); } }
Output:
E:\>javac [Link]

E:\>java SelectionSortDemo

Enter the number of elements : 6

Enter the elements of the array:

21

34

65

23

45

50

Unsorted array: 21 34 65 23 45 50

Sorted array: 21 23 34 45 50 65
//Program 10(c): Insertion Sort

import [Link];
public class InsertionSortDemo {
public static void insertionSort(int array[]) {
int n = [Link];
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j-1;
while ( (i> -1) && ( array [i] > key ) ) {
array [i+1] = array [i];
i--;
}
array[i+1] = key;
}
}

public static void main(String a[])

{
int n;
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of elements : ");
n=[Link]();
int[] arr = new int[n];
[Link]("Enter the elements of the array: ");
for(int i=0; i<n; i++)

//reading array elements from the user

arr[i]=[Link]();
[Link]("Before Insertion Sort");
for(int i:arr){
[Link](i+" ");
}
[Link]();
insertionSort(arr);//sorting array using insertion sort
[Link]("After Insertion Sort");
for(int i:arr){
[Link](i+" ");
}
}
}
Output:

E:\>javac [Link]

E:\>java InsertionSortDemo

Enter the number of elements : 6

Enter the elements of the array:

12

54

34

23

10

87

Before Insertion Sort

12 54 34 23 10 87

After Insertion Sort

10 12 23 34 54 87
//Program 10(d):Radix Sort
import [Link];
class RadixSortDemo
{
public static void main(String[] args)
{
//int[] a = { 3305, 99, 52367, 125, 10, 12345, 7, 35, 7509, 3, 345 };
int n;
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of elements : ");
n=[Link]();
int[] arr = new int[n];
[Link]("Enter the elements of the array: ");
for(int i=0; i<n; i++)
{
//reading array elements from the user
arr[i]=[Link]();
}
radixSort(arr, 10, 5);
[Link]("Sorted list: ");
for(int i = 0; i< n; i++ )
[Link]( arr[i] + " ");
}
static void radixSort(int[] arr, int radix, int maxDigits)
{
int d, j, k, m, divisor;
[Link][] queue = new [Link][radix];
for( d = 0; d < radix; d++ )
queue[d] = new [Link]();
divisor = 1;
for(d = 1; d <= maxDigits; d++) // Pass: 1, 2, 3, . . .
{
for(j = 0; j <[Link]; j++)
{
m = (arr[j]/divisor) % radix;
queue[m].addLast(new Integer(arr[j]));
}
divisor = divisor*radix; // 1, 10, 100, ...
for(j = k = 0; j < radix; j++)
{
while( !queue[j].isEmpty())
arr[k++] = (Integer)queue[j].removeFirst();
}
}
}
}
Output:
E:\>javac [Link]

E:\>java RadixSortDemo

Enter the number of elements : 10

Enter the elements of the array:

34

23

14

29

45

15

30

21

76

54

Sorted list:

14 15 21 23 29 30 34 45 54 76