1.

Write C++ programs to implement the following using an array

a) Stack ADT :
#include<iostream>
#include<conio.h>
using namespace std;
class Stack
{
int stk[10];
int top;
public:
Stack()
{
top=-1;
}

//This funtion is used to push an elemnt into stack

void push(int x)
{
if(isFull())
{
cout <<"Stack is full";
return;
}
top++;
stk[top]=x;
cout <<"Inserted Element:"<<" "<<x;
}

//This functionn is used to check if the stack is full

bool isFull()
{
int size=sizeof(stk)/sizeof(*stk);
if(top == size-1)
{
return true;
}
else
{
return false;
}
}
 //This function is used to check if the stack is empty
bool isEmpty()
{
if(top==-1)
{
return true;
}
else
{
return false;
}
}

//This function is used to pop an element of stack

void pop()
{
if(isEmpty())
{
cout <<"Stack is Empty";
return;
}
cout <<"Deleted element is:" <<" "<<stk[top--];
}

//This function is used to display the elements of the stack

void display()
{
if(top==-1)
{
cout <<" Stack is Empty!!";
return;
}
for(int i=top;i>=0;i--)
{
cout <<stk[i] <<" ";
}
}
};

void main()
{
 int ch;
Stack st;
while(1)
{
cout <<"\n1.Push 2.Pop 3.Display 4.Exit\nEnter ur choice";
cin >> ch;
switch(ch)
{
case 1: cout <<"Enter the element you want to push";
cin >> ch;
st.push(ch);
break;
case 2: st.pop();
break;
case 3: st.display();
break;
case 4: return 0;

}
}
}
Output :-
b) Queue ADT:

#include <iostream>
using namespace std;
int queue[100], n = 100, front = - 1, rear = - 1;
void Insert() {
int val;
if (rear == n - 1)
cout<<"Queue Overflow"<<endl;
else {
if (front == - 1)
front = 0;
cout<<"Insert the element in queue : "<<endl;
cin>>val;
rear++;
queue[rear] = val;
}
}
void Delete() {
if (front == - 1 || front > rear) {
cout<<"Queue Underflow ";
return ;
} else {
cout<<"Element deleted from queue is : "<< queue[front] <<endl;
front++;;
}
}
void Display() {
if (front == - 1)
cout<<"Queue is empty"<<endl;
else {
cout<<"Queue elements are : ";
for (int i = front; i <= rear; i++)
cout<<queue[i]<<" ";
cout<<endl;
}
}
int main() {
int ch;
cout<<"1) Insert element to queue"<<endl;
cout<<"2) Delete element from queue"<<endl;
cout<<"3) Display all the elements of queue"<<endl;
 cout<<"4) Exit"<<endl;
do {
cout<<"Enter your choice : "<<endl;
cin>>ch;
switch (ch) {
case 1: Insert();
break;
case 2: Delete();
break;
case 3: Display();
break;
case 4: cout<<"Exit"<<endl;
break;
default: cout<<"Invalid choice"<<endl;
}
} while(ch!=4);
return 0;
}
Output:
2.Write a C++ program to implement Circular queue using array.
#include<iostream>
#include<bits/stdc++.h>
using namespace std;

class CQueue
{
public:
int *array,Size;
int front,back;
CQueue(int size)
{
Size=size;array= new int[size];
front = back = –1;
}

int isFull()
{
if((front==back+1)||(front == 0 &&back== Size– 1))
return 1;
return 0;
}
int isEmpty()
{
if (front == –1) return 1;
return 0;
}

void enqueue(int value)

{
cout<<“Pushing the value : “<<value<<endl;
if (isFull())
cout<<“Can not push “<<value<<“, The Circular Queue is Full.”<<endl;
else
{
if (front == –1) front = 0;
back = (back + 1) % Size;
array[back] = value;
}
}

int dequeue()
{
int element;
if (isEmpty()) {
cout<<“The Circular Queue is empty.”<<endl;
return –1;
}
element = array[front];
if (front ==back) {
front = –1;
back = –1;
}

else {
front = (front + 1) % Size;
}
cout<<“Popping out the value : “<<element<<endl;
return element;

void Show(){
int i;
if (isEmpty()) cout<<“The Circular Queue is empty.”<<endl;
else
{
cout<<“The Circular Queue is :”<<endl;
for (i=front; i!=back;i= (i+1)%Size)
cout<<array*i+<<” “;
cout<<array[i]<<endl;
}
}
};

int main() {

CQueue CQ(6);
CQ.enqueue(2);CQ.enqueue(7);
CQ.enqueue(3);CQ.enqueue(9);
CQ.Show();
CQ.enqueue(8);CQ.enqueue(4);
CQ.enqueue(1);
CQ.dequeue();
 CQ.enqueue(10);CQ.dequeue();
CQ.Show();

return 0;
}

3.Write C++ programs to implement the following using a single linked list.
a) Stack ADT
#include <iostream>
#include<stdlib.h>
using namespace std;
struct Node {
int data;
struct Node *next;
};
struct Node* top = NULL;
void push(int val) {
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newnode->data = val;
newnode->next = top;
top = newnode;
}
void pop() {
if(top==NULL)
cout<<"Stack Underflow"<<endl;
else {
cout<<"The popped element is "<< top->data <<endl;
top = top->next;
 }
}
void display() {
struct Node* ptr;
if(top==NULL)
cout<<"stack is empty";
else {
ptr = top;
cout<<"Stack elements are: ";
while (ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}
cout<<endl;
}
int main() {
int ch, val;
cout<<"1) Push in stack"<<endl;
cout<<"2) Pop from stack"<<endl;
cout<<"3) Display stack"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter choice: "<<endl;
cin>>ch;
switch(ch) {
case 1: {
cout<<"Enter value to be pushed:"<<endl;
cin>>val;
push(val);
break;
}
case 2: {
pop();
break;
}
case 3: {
display();
break;
}
case 4: {
cout<<"Exit"<<endl;
 break;
}
default: {
cout<<"Invalid Choice"<<endl;
}
}
}while(ch!=4);
return 0;
}

b) Queue ADT:

#include <iostream>
#include<stdlib.h>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node* front = NULL;
struct node* rear = NULL;
struct node* temp;
void Insert() {
int val;
cout<<"Insert the element in queue : "<<endl;
cin>>val;
if (rear == NULL) {
rear = (struct node *)malloc(sizeof(struct node));
rear->next = NULL;
rear->data = val;
front = rear;
} else {
temp=(struct node *)malloc(sizeof(struct node));
rear->next = temp;
temp->data = val;
temp->next = NULL;
rear = temp;
}
}
void Delete() {
temp = front;
if (front == NULL) {
cout<<"Underflow"<<endl;
return;
}
else
if (temp->next != NULL) {
temp = temp->next;
cout<<"Element deleted from queue is : "<<front->data<<endl;
free(front);
front = temp;
 } else {
cout<<"Element deleted from queue is : "<<front->data<<endl;
free(front);
front = NULL;
rear = NULL;
}
}
void Display() {
temp = front;
if ((front == NULL) && (rear == NULL)) {
cout<<"Queue is empty"<<endl;
return;
}
cout<<"Queue elements are: ";
while (temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl;
}
int main() {
int ch;
cout<<"1) Insert element to queue"<<endl;
cout<<"2) Delete element from queue"<<endl;
cout<<"3) Display all the elements of queue"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter your choice : "<<endl;
cin>>ch;
switch (ch) {
case 1: Insert();
break;
case 2: Delete();
 break;
case 3: Display();
break;
case 4: cout<<"Exit"<<endl;
break;
default: cout<<"Invalid choice"<<endl;
}
} while(ch!=4);
return 0;
}
4. Write a C++ program to implement Circular queue using Single linked list.

#include <iostream>
using namespace std;

int cqueue[5];
int front = -1, rear = -1, n=5;

void insertCQ(int val) {

if ((front == 0 && rear == n-1) || (front == rear+1)) {
cout<<"Queue Overflow \n";
return;
}
if (front == -1) {
front = 0;
rear = 0;
} else {
if (rear == n - 1)
rear = 0;
else
rear = rear + 1;
}
cqueue[rear] = val ;
}
void deleteCQ() {
if (front == -1) {
cout<<"Queue Underflow\n";
return ;
}
cout<<"Element deleted from queue is : "<<cqueue[front]<<endl;

if (front == rear) {
front = -1;
rear = -1;
 } else {
if (front == n - 1)
front = 0;
else
front = front + 1;
}
}
void displayCQ() {
int f = front, r = rear;
if (front == -1) {
cout<<"Queue is empty"<<endl;
return;
}
cout<<"Queue elements are :\n";
if (f <= r) {
while (f <= r){
cout<<cqueue[f]<<" ";
f++;
}
} else {
while (f <= n - 1) {
cout<<cqueue[f]<<" ";
f++;
}
f = 0;
while (f <= r) {
cout<<cqueue[f]<<" ";
f++;
}
}
cout<<endl;
}
int main() {
 int ch, val;
cout<<"1)Insert\n";
cout<<"2)Delete\n";
cout<<"3)Display\n";
cout<<"4)Exit\n";
do {
cout<<"Enter choice : "<<endl;
cin>>ch;
switch(ch) {
case 1:
cout<<"Input for insertion: "<<endl;
cin>>val;
insertCQ(val);
break;

case 2:
deleteCQ();
break;

case 3:
displayCQ();
break;

case 4:
cout<<"Exit\n";
break;
default: cout<<"Incorrect!\n";
}
} while(ch != 4);
return 0;
}
5. Write a C++ program to implement the double ended queue ADT using double linked list

#include<bits/stdc++.h>
using namespace std;
// class representing a tree node
class Node {
public:
int data;
Node *next;
Node *prev;

Node(int d) {
data = d;
next = NULL;
prev = NULL;
}
};
// function to create a new node
Node* newNode(int x) {
Node *node = new Node(x);
return node;
}
// front points to start of Deque and rear points to the end of Deque
Node *front = NULL;
Node *rear = NULL;
// Variable representing size of Deque
int Size = 0;
void insertFront(int x) {
// Create a new Node with required parameters
Node *node = newNode(x);
if (front == NULL) {
// This is the first node to be inserted
front = rear = node;
} else {
// Add the node before front
node->next = front;
front->prev = node;
// update front
front = node;
}
// Increment size
Size++;
}
void insertEnd(int x) {
// Create a new Node with required parameters
Node *node = newNode(x);
 if (rear == NULL) {
// This is the first node to be inserted
front = rear = node;
} else {
// Insert the node after rear
node->prev = rear;
rear->next = node;
// update rear
rear = node;
}
// Increment size
Size++;
}
void deleteFront() {
if (front == NULL) {
// no node to delete
return;
}
if (front == rear) {
// only 1 node is present
front = rear = NULL;
} else {
// delete front and move front ahead
Node *temp = front;
front = front->next;
front->prev = NULL;
// deallocate the memory taken by temp
delete(temp);
}
// Decrement size
Size--;
}
void deleteEnd() {
if (rear == NULL) {
// no node to delete
return;
}
if (front == rear) {
// only 1 node is present
front = rear = NULL;
} else {
// delete rear and move rear backwards
Node *temp = rear;
rear = rear->prev;
rear->next = NULL;
// deallocate the memory taken by temp
delete(temp);
}
 // Decrement size
Size--;
}
int getFront() {
if (front != NULL) {
return front->data;
}
return -1;
}
int getEnd() {
if (rear != NULL) {
return rear->data;
}
return -1;
}
int size() {
return Size;
}
bool isEmpty() {
if (front == NULL) {
return true;
}
return false;
}
void erase() {
// mark rear as null
rear = NULL;
// traverse the doubly linked list
while (front != NULL) {
Node *temp = front;
// delete all the prev pointers
front->prev = NULL;
front = front->next;
// Deallocate the memory taken by temp
delete(temp);
}
// Set size as 0
Size = 0;
}
int main() {
// Example
insertFront(5); // 5
insertEnd(10); // 5 <-> 10
insertEnd(11); // 5 <-> 10 <-> 11
insertFront(19); // 19 <-> 5 <-> 10 <-> 11
cout<<getFront()<<endl;
cout<<getEnd()<<endl;
deleteEnd(); // 19 <-> 5 <-> 10
 cout<<getEnd()<<endl;
deleteFront(); // 5 <-> 10
cout<<getFront()<<endl;
cout<<size()<<endl;
if (isEmpty()) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
erase();
if (isEmpty()) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}

return 0;
}
6. Write a C++ program to solve tower of Hanoi problem recursively

#include<iostream.h>
#include<conio.h>
using namespace std;
void TOH(int d, char t1, char t2, char t3)
{
if(d==1)
{
cout<<"\nShift top disk from tower"<<t1<<" to tower"<<t2;
return;
}
TOH(d-1,t1,t3,t2);
cout<<"\nShift top disk from tower"<<t1<<" to tower"<<t2;
TOH(d-1,t3,t2,t1);
}
int main()
{
int disk;
cout<<"Enter the number of disks:"; cin>>disk;
if(disk<1)
cout<<"There are no disks to shift";
else
cout<<"There are "<<disk<<"disks in tower 1\n";
TOH(disk, '1','2','3');
cout<<"\n\n"<<disk<<"disks in tower 1 are shifted to tower 2";
getch();
return 0;
}
7. Write C++ program to perform the following operations:

a) Insert an element into a binary search tree.

b) Delete an element from binary search tree.

c) Search for a key in a binary search tree.

# include <iostream>
# include <cstdlib>
using namespace std;
struct nod//node declaration
{
int info;
struct nod *l;
struct nod *r;
}*r;
class BST
{
public://functions declaration
void search(nod *, int);
void insert(nod *, nod *);
void del(int);
void show(nod *, int);
BST()
{
r = NULL;
}
};
void BST::search(nod *root, int data) //searching
{
int depth = 0;
nod *temp = new nod;
temp = root;
while(temp != NULL)
 {
depth++;
if(temp→info == data)
{
cout<<"\nData found at depth: "<<depth<<endl;
return;
}
else if(temp→info > data)
temp = temp→l;
else
temp = temp→r;
}
cout<<"\n Data not found"<<endl;
return;
}
void BST::insert(nod *tree, nod *newnode)
{
if (r == NULL)
{
r = new nod;
r→info = newnode→info;
r→l= NULL;
r→r= NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree→info == newnode→info)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (tree→info > newnode→info)
{
 if (tree→l != NULL)
{
insert(tree→l, newnode);
}
else
{
tree→l= newnode;
(tree→l)→l = NULL;
(tree→l)→r= NULL;
cout<<"Node Added To Left"<<endl;
return;
}
}
else
{
if (tree→r != NULL)
{
insert(tree→r, newnode);
}
else
{
tree→r = newnode;
(tree→r)→l= NULL;
(tree→r)→r = NULL;
cout<<"Node Added To Right"<<endl;
return;
}
}
}
void BST::del(int i)
{
nod *par, *loc;
if (r == NULL)
 {
cout<<"Tree empty"<<endl;
return;
}
find(i, &par, &loc);
if (loc == NULL)
{
cout<<"Item not present in tree"<<endl;
return;
}
if (loc→l == NULL && loc→r == NULL)
{
casea(par, loc);
cout<<"item deleted"<<endl;
}
if (loc→l!= NULL && loc→r == NULL)
{
caseb(par, loc);
cout<<"item deleted"<<endl;
}
if (loc→l== NULL && loc→r != NULL)
{
caseb(par, loc);
cout<<"item deleted"<<endl;
}
if (loc→l != NULL && loc→r != NULL)
{
casec(par, loc);
cout<<"item deleted"<<endl;
}
free(loc);
}
void BST::show(nod *ptr, int level)//print the tree
{
int i;
if (ptr != NULL)
{
show(ptr→r, level+1);
cout<<endl;
if (ptr == r)
cout<<"Root→: ";
else
{
for (i = 0;i < level;i++)
cout<<" ";
}
cout<<ptr→info;
show(ptr→l, level+1);
}
}
int main()
{
int c, n,item;
BST bst;
nod *t;
while (1)
{
cout<<"1.Insert Element "<<endl;
cout<<"2.Delete Element "<<endl;
cout<<"3.Search Element"<<endl;
cout<<"4.Display the tree"<<endl;
cout<<"5.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>c;
switch(c)
{
 case 1:
t = new nod;
cout<<"Enter the number to be inserted : ";
cin>>t→info;
bst.insert(r, t);
break;
case 2:
if (r == NULL)
{
cout<<"Tree is empty, nothing to delete"<<endl;
continue;
}
cout<<"Enter the number to be deleted : ";
cin>>n;
bst.del(n);
break;
case 3:
cout<<"Search:"<<endl;
cin>>item;
bst.search(r,item);
break;
case 4:
cout<<"Display BST:"<<endl;
bst.show(r,1);
cout<<endl;
break;
case 5:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
}
8. Write C++ programs for the implementation tree traversal technique BFS.

#include<iostream>
#include<conio.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node* newNode(int data) {
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int main() {
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << "Level Order traversal of binary tree is \n";
queue<Node *> q;
q.push(root);
while (q.empty() == false) {
Node *node = q.front();
cout << node->data << " ";
q.pop();
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
}
return 0;
}

9. Write a C++ program that uses recursive functions to traverse a binary search tree.
a) Pre-order
#include<iostream>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}
void preorder(struct node *root) {
if (root != NULL) {
cout<<root->data<<" ";
preorder(root->left);
preorder(root->right);
}
}
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
}
int main() {
struct node *root = NULL;
root = insertNode(root, 4);
insertNode(root, 5);
insertNode(root, 2);
insertNode(root, 9);
insertNode(root, 1);
insertNode(root, 3);
cout<<"Pre-Order traversal of the Binary Search Tree is: ";
preorder(root);
return 0; }
b) In-order
#include<iostream>
using namespace std;
struct node {
 int data;
struct node *left;
struct node *right;
};
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}
void inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
}
int main() {
struct node *root = NULL;
root = insertNode(root, 4);
insertNode(root, 5);
insertNode(root, 2);
insertNode(root, 9);
insertNode(root, 1);
insertNode(root, 3);
cout<<"In-Order traversal of the Binary Search Tree is: ";
inorder(root);
return 0;
}

c) Post-order
#include<iostream>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
struct node *createNode(int val) {
 struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}
void postorder(struct node *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
}
}
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
}
int main() {
struct node *root = NULL;
root = insertNode(root, 4);
insertNode(root, 5);
insertNode(root, 2);
insertNode(root, 9);
insertNode(root, 1);
insertNode(root, 3);
cout<<"Post-Order traversal of the Binary Search Tree is: ";
postorder(root);
return 0;
}
10. Write a C++ program to find height of a tree.
#include<iostream>
using namespace std;
// structure of node
struct Node
{
Node *left; // Pointer to left sub-tree
int element; // Value
Node *right; // Pointer to right sub-tree
Node(int theElement,Node *theLeft,Node *theRight)
{
element = theElement;
left = theLeft;
right = theRight;
}
};
 int height(Node *root)
{
int h = 0;
if(root != NULL)
{
int lHeight = height(root->left);
int rHeight = height(root->right);
int maxHeight = max(lHeight,rHeight);
h = maxHeight + 1;
}
return h;
}
int main()
{
// creating a binary tree with 5 nodes
Node *n1,*n2,*n3,*n4,*n5;
n1 = new Node(5,NULL,NULL);
n2 = new Node(7,NULL,NULL);
n3 = new Node(6,n1,n2);
n4 = new Node(9,NULL,NULL);
n5 = new Node(3,n3,n4);

cout << "Height of the tree is " << height(n5) << endl;
return 0;
}

11 Write a C++ program to find MIN and MAX element of a BST.

#include <bits/stdc++.h>
using namespace std;

struct node
{
int key;
struct node *left, *right;
};

// A utility function to create a new BST node

struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

/* A utility function to insert a new node with given key in BST */

struct node* insert(struct node* node, int key)
{
 struct node *newNode(int );
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);

/* Otherwise, recur down the tree */

if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);

/* return the (unchanged) node pointer */

return node;
}
/* 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. */
int minValue(struct node* node)
{
struct node* current = node;

/* loop down to find the leftmost leaf */

while (current->left != NULL)
{
current = current->left;
}
return(current->key);
}
/* Given a non-empty binary search tree,
return the maximum data value found in that
tree. Note that the entire tree does not need
to be searched. */
int maxValue(struct node* node)
{
struct node* current = node;

/* loop down to find the leftmost leaf */

while (current->right != NULL)
{
current = current->right;
}
return(current->key);
}
// Driver Program to test above functions
int main()
{
int maxValue(struct node* );
struct node* insert(struct node* , int );
 int minValue(struct node* );
struct node *root = NULL;
root = insert(root, 8);
insert(root, 3);
insert(root, 10);
insert(root, 1);
insert(root, 6);
insert(root, 4);
insert(root, 7);
insert(root, 5);
insert(root, 10);
insert(root, 9);
insert(root, 13);
insert(root, 11);
insert(root, 14);
insert(root, 12);
insert(root, 2);

cout << "\n Minimum value in BST is " << minValue(root)<<endl;

cout << "\n Maximum value in BST is " << maxValue(root);
return 0;
}

12 Write a C++ program to find Inorder Successor of a given node.

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
if(!root) return NULL;
if(root->val <= p->val){
return inorderSuccessor(root->right, p);
}else{
TreeNode* option = inorderSuccessor(root->left, p);
return !option ? root : option;
}
 }
};
main(){
TreeNode *root = new TreeNode(2);
root->left = new TreeNode(1);
root->right = new TreeNode(3);
TreeNode *p = root->left;
Solution ob;
cout << (ob.inorderSuccessor(root, p))->val;
}

13. Write C++ programs to perform the following operations on B-Trees and AVL Trees.

a) Insertion

// C++ program to insert a node in AVL tree

#include<bits/stdc++.h>
using namespace std;

// An AVL tree node

class Node
{
public:
int key;
Node *left;
Node *right;
int height;
};

// A utility function to get maximum

// of two integers
int max(int a, int b);

// A utility function to get the

// height of the tree
int height(Node *N)
{
if (N == NULL)
return 0;
return N->height;
}

// A utility function to get maximum

// of two integers
int max(int a, int b)
{
return (a > b)? a : b;
}

/* Helper function that allocates a

new node with the given key and
NULL left and right pointers. */
Node* newNode(int key)
{
Node* node = new Node();
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially
// added at leaf
return(node);
}

// A utility function to right

// rotate subtree rooted with y
// See the diagram given above.
Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *T2 = x->right;

// Perform rotation
x->right = y;
y->left = T2;

// Update heights
y->height = max(height(y->left),
height(y->right)) + 1;
x->height = max(height(x->left),
height(x->right)) + 1;

// Return new root

return x;
}

// A utility function to left

// rotate subtree rooted with x
// See the diagram given above.
Node *leftRotate(Node *x)
{
Node *y = x->right;
Node *T2 = y->left;

// Perform rotation
y->left = x;
 x->right = T2;

// Update heights
x->height = max(height(x->left),
height(x->right)) + 1;
y->height = max(height(y->left),
height(y->right)) + 1;

// Return new root

return y;
}

// Get Balance factor of node N

int getBalance(Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}

// Recursive function to insert a key

// in the subtree rooted with node and
// returns the new root of the subtree.
Node* insert(Node* node, int key)
{
/* 1. Perform the normal BST insertion */
if (node == NULL)
return(newNode(key));

if (key < node->key)

node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys are not allowed in BST
return node;

/* 2. Update height of this ancestor node */

node->height = 1 + max(height(node->left),
height(node->right));

/* 3. Get the balance factor of this ancestor

node to check whether this node became
unbalanced */
int balance = getBalance(node);

// If this node becomes unbalanced, then

// there are 4 cases
 // Left Left Case
if (balance > 1 && key < node->left->key)
return rightRotate(node);

// Right Right Case

if (balance < -1 && key > node->right->key)
return leftRotate(node);

// Left Right Case

if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}

// Right Left Case

if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}

/* return the (unchanged) node pointer */

return node;
}

// A utility function to print preorder

// traversal of the tree.
// The function also prints height
// of every node
void preOrder(Node *root)
{
if(root != NULL)
{
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}

// Driver Code
int main()
{
Node *root = NULL;

/* Constructing tree given in

the above figure */
root = insert(root, 10);
 root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);

/* The constructed AVL Tree would be

30
/\
20 40
/\\
10 25 50
*/
cout << "Preorder traversal of the "
"constructed AVL tree is \n";
preOrder(root);

return 0;
}

b) Deletion

// C++ program to delete a node from AVL Tree

#include<bits/stdc++.h>
using namespace std;

// An AVL tree node

class Node
{
public:
int key;
Node *left;
Node *right;
int height;
};

// A utility function to get maximum

// of two integers
int max(int a, int b);

// A utility function to get height

// of the tree
int height(Node *N)
{
if (N == NULL)
 return 0;
return N->height;
}

// A utility function to get maximum

// of two integers
int max(int a, int b)
{
return (a > b)? a : b;
}

/* Helper function that allocates a

new node with the given key and
NULL left and right pointers. */
Node* newNode(int key)
{
Node* node = new Node();
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially
// added at leaf
return(node);
}

// A utility function to right

// rotate subtree rooted with y
// See the diagram given above.
Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *T2 = x->right;

// Perform rotation
x->right = y;
y->left = T2;

// Update heights
y->height = max(height(y->left),
height(y->right)) + 1;
x->height = max(height(x->left),
height(x->right)) + 1;

// Return new root

return x;
}

// A utility function to left

// rotate subtree rooted with x
// See the diagram given above.
Node *leftRotate(Node *x)
{
Node *y = x->right;
Node *T2 = y->left;

// Perform rotation
y->left = x;
x->right = T2;

// Update heights
x->height = max(height(x->left),
height(x->right)) + 1;
y->height = max(height(y->left),
height(y->right)) + 1;

// Return new root

return y;
}

// Get Balance factor of node N

int getBalance(Node *N)
{
if (N == NULL)
return 0;
return height(N->left) -
height(N->right);
}

Node* insert(Node* node, int key)

{
/* 1. Perform the normal BST rotation */
if (node == NULL)
return(newNode(key));

if (key < node->key)

node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys not allowed
return node;

/* 2. Update height of this ancestor node */

node->height = 1 + max(height(node->left),
height(node->right));

/* 3. Get the balance factor of this

 ancestor node to check whether
this node became unbalanced */
int balance = getBalance(node);

// If this node becomes unbalanced,

// then there are 4 cases

// Left Left Case

if (balance > 1 && key < node->left->key)
return rightRotate(node);

// Right Right Case

if (balance < -1 && key > node->right->key)
return leftRotate(node);

// Left Right Case

if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}

// Right Left Case

if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}

/* return the (unchanged) node pointer */

return node;
}

/* Given a non-empty binary search tree,

return the node with minimum key value
found in that tree. Note that the entire
tree does not need to be searched. */
Node * minValueNode(Node* node)
{
Node* current = node;

/* loop down to find the leftmost leaf */

while (current->left != NULL)
current = current->left;

return current;
}
// Recursive function to delete a node
// with given key from subtree with
// given root. It returns root of the
// modified subtree.
Node* deleteNode(Node* root, int key)
{

// STEP 1: PERFORM STANDARD BST DELETE

if (root == NULL)
return root;

// If the key to be deleted is smaller

// than the root's key, then it lies
// in left subtree
if ( key < root->key )
root->left = deleteNode(root->left, key);

// If the key to be deleted is greater

// than the root's key, then it lies
// in right subtree
else if( key > root->key )
root->right = deleteNode(root->right, key);

// if key is same as root's key, then

// This is the node to be deleted
else
{
// node with only one child or no child
if( (root->left == NULL) ||
(root->right == NULL) )
{
Node *temp = root->left ?
root->left :
root->right;

// No child case
if (temp == NULL)
{
temp = root;
root = NULL;
}
else // One child case
*root = *temp; // Copy the contents of
// the non-empty child
free(temp);
}
else
{
 // node with two children: Get the inorder
// successor (smallest in the right subtree)
Node* temp = minValueNode(root->right);

// Copy the inorder successor's

// data to this node
root->key = temp->key;

// Delete the inorder successor

root->right = deleteNode(root->right,
temp->key);
}
}

// If the tree had only one node

// then return
if (root == NULL)
return root;

// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE

root->height = 1 + max(height(root->left),
height(root->right));

// STEP 3: GET THE BALANCE FACTOR OF

// THIS NODE (to check whether this
// node became unbalanced)
int balance = getBalance(root);

// If this node becomes unbalanced,

// then there are 4 cases

// Left Left Case

if (balance > 1 &&
getBalance(root->left) >= 0)
return rightRotate(root);

// Left Right Case

if (balance > 1 &&
getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}

// Right Right Case

if (balance < -1 &&
getBalance(root->right) <= 0)
return leftRotate(root);
 // Right Left Case
if (balance < -1 &&
getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}

return root;
}

// A utility function to print preorder

// traversal of the tree.
// The function also prints height
// of every node
void preOrder(Node *root)
{
if(root != NULL)
{
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}

// Driver Code
int main()
{
Node *root = NULL;

/* Constructing tree given in

the above figure */
root = insert(root, 9);
root = insert(root, 5);
root = insert(root, 10);
root = insert(root, 0);
root = insert(root, 6);
root = insert(root, 11);
root = insert(root, -1);
root = insert(root, 1);
root = insert(root, 2);

/* The constructed AVL Tree would be

9
/\
1 10
/\\
 0 5 11
//\
-1 2 6
*/

cout << "Preorder traversal of the "

"constructed AVL tree is \n";
preOrder(root);

root = deleteNode(root, 10);

/* The AVL Tree after deletion of 10

1
/\
09
//\
-1 5 11
/\
26
*/

cout << "\nPreorder traversal after"

<< " deletion of 10 \n";
preOrder(root);

return 0;
}

14 Write C++ programs for sorting a given list of elements in ascending order using the
following sorting methods.

a) Quick sort

#include <iostream>
using namespace std;

int partition(int arr[], int start, int end)

{

int pivot = arr[start];

int count = 0;
for (int i = start + 1; i <= end; i++) {
 if (arr[i] <= pivot)
count++;
}

// Giving pivot element its correct position

int pivotIndex = start + count;
swap(arr[pivotIndex], arr[start]);

// Sorting left and right parts of the pivot element

int i = start, j = end;

while (i < pivotIndex && j > pivotIndex) {

while (arr[i] <= pivot) {

i++;
}

while (arr[j] > pivot) {

j--;
}

if (i < pivotIndex && j > pivotIndex) {

swap(arr[i++], arr[j--]);
}
}

return pivotIndex;
}

void quickSort(int arr[], int start, int end)

{

// base case
if (start >= end)
return;

// partitioning the array

int p = partition(arr, start, end);

// Sorting the left part

quickSort(arr, start, p - 1);

// Sorting the right part

quickSort(arr, p + 1, end);
}

int main()
{
 int arr[] = { 9, 3, 4, 2, 1, 8 };
int n = 6;

quickSort(arr, 0, n - 1);

for (int i = 0; i < n; i++) {

cout << arr[i] << " ";
}

return 0;
}

b) Merge sort
#include<iostream>
using namespace std;
void swapping(int &a, int &b) { //swap the content of a and b
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void merge(int *array, int l, int m, int r) {
int i, j, k, nl, nr;
//size of left and right sub-arrays
nl = m-l+1; nr = r-m;
int larr[nl], rarr[nr];
//fill left and right sub-arrays
for(i = 0; i<nl; i++)
larr[i] = array[l+i];
for(j = 0; j<nr; j++)
rarr[j] = array[m+1+j];
i = 0; j = 0; k = l;
//marge temp arrays to real array
while(i < nl && j<nr) {
if(larr[i] <= rarr[j]) {
array[k] = larr[i];
i++;
}else{
array[k] = rarr[j];
j++;
}
 k++;
}
while(i<nl) { //extra element in left array
array[k] = larr[i];
i++; k++;
}
while(j<nr) { //extra element in right array
array[k] = rarr[j];
j++; k++;
}
}
void mergeSort(int *array, int l, int r) {
int m;
if(l < r) {
int m = l+(r-l)/2;
// Sort first and second arrays
mergeSort(array, l, m);
mergeSort(array, m+1, r);
merge(array, l, m, r);
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
mergeSort(arr, 0, n-1); //(n-1) for last index
cout << "Array after Sorting: ";
display(arr, n);
}
15. Write a C++ program to find optimal ordering of matrix multiplication.

#include<iostream>
#include<limits.h>

using namespace std;

// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n

int MatrixChainMultiplication(int p[], int n)

{
int m[n][n];
int i, j, k, L, q;

for (i=1; i<n; i++)

m[i][i] = 0; //number of multiplications are 0(zero) when there is only one matrix

//Here L is chain length. It varies from length 2 to length n.

for (L=2; L<n; L++)
{
for (i=1; i<n-L+1; i++)
{
j = i+L-1;
m[i][j] = INT_MAX; //assigning to maximum value

for (k=i; k<=j-1; k++)

{
q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (q < m[i][j])
{
m[i][j] = q; //if number of multiplications found less that number will be updated.
}
}
}
}

return m[1][n-1]; //returning the final answer which is M[1][n]

int main()
{
int n,i;
cout<<"Enter number of matrices\n";
cin>>n;

n++;
 int arr[n];

cout<<"Enter dimensions \n";

for(i=0;i<n;i++)
{
cout<<"Enter d"<<i<<" :: ";
cin>>arr[i];
}

int size = sizeof(arr)/sizeof(arr[0]);

cout<<"Minimum number of multiplications is "<<MatrixChainMultiplication(arr, size));

return 0;
}
16. Write a C++ program that uses dynamic programming algorithm to solve the optimal
binary search tree problem.

// A naive recursive implementation of

// optimal binary search tree problem

#include <bits/stdc++.h>
using namespace std;

// A utility function to get sum of

// array elements freq[i] to freq[j]
int sum(int freq[], int i, int j);

// A recursive function to calculate

// cost of optimal binary search tree
int optCost(int freq[], int i, int j)
{
// Base cases
if (j < i) // no elements in this subarray
return 0;
if (j == i) // one element in this subarray
return freq[i];

// Get sum of freq[i], freq[i+1], ... freq[j]

int fsum = sum(freq, i, j);

// Initialize minimum value

int min = INT_MAX;

// One by one consider all elements

// as root and recursively find cost
 // of the BST, compare the cost with
// min and update min if needed
for (int r = i; r <= j; ++r)
{
int cost = optCost(freq, i, r - 1) +
optCost(freq, r + 1, j);
if (cost < min)
min = cost;
}

// Return minimum value

return min + fsum;
}

// The main function that calculates

// minimum cost of a Binary Search Tree.
// It mainly uses optCost() to find
// the optimal cost.
int optimalSearchTree(int keys[],
int freq[], int n)
{
// Here array keys[] is assumed to be
// sorted in increasing order. If keys[]
// is not sorted, then add code to sort
// keys, and rearrange freq[] accordingly.
return optCost(freq, 0, n - 1);
}

// A utility function to get sum of

// array elements freq[i] to freq[j]
int sum(int freq[], int i, int j)
{
int s = 0;
for (int k = i; k <= j; k++)
s += freq[k];
return s;
}

// Driver Code
int main()
{
int keys[] = {10, 12, 20};
int freq[] = {34, 8, 50};
int n = sizeof(keys) / sizeof(keys[0]);
cout << "Cost of Optimal BST is "
<< optimalSearchTree(keys, freq, n);
return 0;
}
17. Write a C++ program to implement Hash Table

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstdio>
using namespace std;
const int T_S = 200;
class HashTableEntry {
public:
int k;
int v;
HashTableEntry(int k, int v) {
this->k= k;
this->v = v;
}
};
class HashMapTable {
private:
HashTableEntry **t;
public:
HashMapTable() {
t = new HashTableEntry * [T_S];
for (int i = 0; i< T_S; i++) {
t[i] = NULL;
}
}
int HashFunc(int k) {
return k % T_S;
}
void Insert(int k, int v) {
int h = HashFunc(k);
while (t[h] != NULL && t[h]->k != k) {
h = HashFunc(h + 1);
}
if (t[h] != NULL)
delete t[h];
t[h] = new HashTableEntry(k, v);
}
int SearchKey(int k) {
int h = HashFunc(k);
while (t[h] != NULL && t[h]->k != k) {
h = HashFunc(h + 1);
}
if (t[h] == NULL)
return -1;
else
return t[h]->v;
 }
void Remove(int k) {
int h = HashFunc(k);
while (t[h] != NULL) {
if (t[h]->k == k)
break;
h = HashFunc(h + 1);
}
if (t[h] == NULL) {
cout<<"No Element found at key "<<k<<endl;
return;
} else {
delete t[h];
}
cout<<"Element Deleted"<<endl;
}
~HashMapTable() {
for (int i = 0; i < T_S; i++) {
if (t[i] != NULL)
delete t[i];
delete[] t;
}
}
};
int main() {
HashMapTable hash;
int k, v;
int c;
while (1) {
cout<<"1.Insert element into the table"<<endl;
cout<<"2.Search element from the key"<<endl;
cout<<"3.Delete element at a key"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>c;
switch(c) {
case 1:
cout<<"Enter element to be inserted: ";
cin>>v;
cout<<"Enter key at which element to be inserted: ";
cin>>k;
hash.Insert(k, v);
break;
case 2:
cout<<"Enter key of the element to be searched: ";
cin>>k;
if (hash.SearchKey(k) == -1) {
cout<<"No element found at key "<<k<<endl;
 continue;
} else {
cout<<"Element at key "<<k<<" : ";
cout<<hash.SearchKey(k)<<endl;
}
break;
case 3:
cout<<"Enter key of the element to be deleted: ";
cin>>k;
hash.Remove(k);
break;
case 4:
exit(1);
default:
cout<<"\nEnter correct option\n";
}
}
return 0;
}

18. Write C++ programs to perform the following on Heap a) Build Heap b) Insertion c)
Deletion

#include <iostream>
#include <cstdlib>
#include <vector>
#include <iterator>
using namespace std;
class BHeap {
private:
vector <int> heap;
int l(int parent);
int r(int parent);
int par(int child);
void heapifyup(int index);
void heapifydown(int index);
public:
BHeap() {}
void Insert(int element);
void DeleteMin();
int ExtractMin();
void showHeap();
int Size();
};
int main() {
BHeap h;
while (1) {
 cout<<"1.Insert Element"<<endl;
cout<<"2.Delete Minimum Element"<<endl;
cout<<"3.Extract Minimum Element"<<endl;
cout<<"4.Show Heap"<<endl;
cout<<"5.Exit"<<endl;
int c, e;
cout<<"Enter your choice: ";
cin>>c;
switch(c) {
case 1:
cout<<"Enter the element to be inserted: ";
cin>>e;
h.Insert(e);
break;
case 2:
h.DeleteMin();
break;
case 3:
if (h.ExtractMin() == -1) {
cout<<"Heap is Empty"<<endl;
}
else
cout<<"Minimum Element: "<<h.ExtractMin()<<endl;
break;
case 4:
cout<<"Displaying elements of Hwap: ";
h.showHeap();
break;
case 5:
exit(1);
default:
cout<<"Enter Correct Choice"<<endl;
}
}
return 0;
}
int BHeap::Size() {
return heap.size();
}
void BHeap::Insert(int ele) {
heap.push_back(ele);
heapifyup(heap.size() -1);
}
void BHeap::DeleteMin() {
if (heap.size() == 0) {
cout<<"Heap is Empty"<<endl;
return;
}
 heap[0] = heap.at(heap.size() - 1);
heap.pop_back();
heapifydown(0);
cout<<"Element Deleted"<<endl;
}
int BHeap::ExtractMin() {
if (heap.size() == 0) {
return -1;
}
else
return heap.front();
}
void BHeap::showHeap() {
vector <int>::iterator pos = heap.begin();
cout<<"Heap --> ";
while (pos != heap.end()) {
cout<<*pos<<" ";
pos++;
}
cout<<endl;
}
int BHeap::l(int parent) {
int l = 2 * parent + 1;
if (l < heap.size())
return l;
else
return -1;
}
int BHeap::r(int parent) {
int r = 2 * parent + 2;
if (r < heap.size())
return r;
else
return -1;
}
int BHeap::par(int child) {
int p = (child - 1)/2;
if (child == 0)
return -1;
else
return p;
}
void BHeap::heapifyup(int in) {
if (in >= 0 && par(in) >= 0 && heap[par(in)] > heap[in]) {
int temp = heap[in];
heap[in] = heap[par(in)];
heap[par(in)] = temp;
heapifyup(par(in));
 }
}
void BHeap::heapifydown(int in) {
int child = l(in);
int child1 = r(in);
if (child >= 0 && child1 >= 0 && heap[child] > heap[child1]) {
child = child1;
}
if (child > 0 && heap[in] > heap[child]) {
int t = heap[in];
heap[in] = heap[child];
heap[child] = t;
heapifydown(child);
}
}
19. Write C++ programs to perform following operations on Skip List

a) Insertion b) Deletion

/*

* C++ Program to Implement Skip List

*/

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#define MAX_LEVEL 6
const float P = 0.5;
using namespace std;
/*
* Skip Node Declaration
*/
struct snode
{
int value;
snode **forw;
snode(int level, int &value)
{
forw = new snode * [level + 1];
memset(forw, 0, sizeof(snode*) * (level + 1));
this->value = value;
}
~snode()
{
delete [] forw;
 }
};
/*
* Skip List Declaration
*/
struct skiplist
{
snode *header;
int value;
int level;
skiplist()
{
header = new snode(MAX_LEVEL, value);
level = 0;
}
~skiplist()
{
delete header;
}
void display();
bool contains(int &);
void insert_element(int &);
void delete_element(int &);
};
/*
* Main: Contains Menu
*/
int main()
{
skiplist ss;
int choice, n;
while (1)
{
cout<<endl<<"-----------------------"<<endl;
cout<<endl<<"Operations on Skip list"<<endl;
cout<<endl<<"-----------------------"<<endl;
cout<<"1.Insert Element"<<endl;
cout<<"2.Delete Element"<<endl;
cout<<"3.Search Element"<<endl;
cout<<"4.Display List "<<endl;
cout<<"5.Exit "<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the element to be inserted: ";
cin>>n;
 ss.insert_element(n);
if(ss.contains(n))
cout<<"Element Inserted"<<endl;
break;
case 2:
cout<<"Enter the element to be deleted: ";
cin>>n;
if(!ss.contains(n))
{
cout<<"Element not found"<<endl;
break;
}
ss.delete_element(n);
if(!ss.contains(n))
cout<<"Element Deleted"<<endl;
break;
case 3:
cout<<"Enter the element to be searched: ";
cin>>n;
if(ss.contains(n))
cout<<"Element "<<n<<" is in the list"<<endl;
else
cout<<"Element not found"<<endl;
case 4:
cout<<"The List is: ";
ss.display();
break;
case 5:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}

/*
* Random Value Generator
*/
float frand()
{
return (float) rand() / RAND_MAX;
}

/*
* Random Level Generator
*/
int random_level()
{
static bool first = true;
if (first)
{
srand((unsigned)time(NULL));
first = false;
}
int lvl = (int)(log(frand()) / log(1.-P));
return lvl < MAX_LEVEL ? lvl : MAX_LEVEL;
}

/*
* Insert Element in Skip List
*/
void skiplist::insert_element(int &value)
{
snode *x = header;
snode *update[MAX_LEVEL + 1];
memset(update, 0, sizeof(snode*) * (MAX_LEVEL + 1));
for (int i = level;i >= 0;i--)
{
while (x->forw[i] != NULL && x->forw[i]->value < value)
{
x = x->forw[i];
}
update[i] = x;
}
x = x->forw[0];
if (x == NULL || x->value != value)
{
int lvl = random_level();
if (lvl > level)
{
for (int i = level + 1;i <= lvl;i++)
{
update[i] = header;
}
level = lvl;
}
x = new snode(lvl, value);
for (int i = 0;i <= lvl;i++)
{
x->forw[i] = update[i]->forw[i];
update[i]->forw[i] = x;
}
}
}
/*
* Delete Element from Skip List
*/
void skiplist::delete_element(int &value)
{
snode *x = header;
snode *update[MAX_LEVEL + 1];
memset (update, 0, sizeof(snode*) * (MAX_LEVEL + 1));
for (int i = level;i >= 0;i--)
{
while (x->forw[i] != NULL && x->forw[i]->value < value)
{
x = x->forw[i];
}
update[i] = x;
}
x = x->forw[0];
if (x->value == value)
{
for (int i = 0;i <= level;i++)
{
if (update[i]->forw[i] != x)
break;
update[i]->forw[i] = x->forw[i];
}
delete x;
while (level > 0 && header->forw[level] == NULL)
{
level--;
}
}
}

/*
* Display Elements of Skip List
*/
void skiplist::display()
{
const snode *x = header->forw[0];
while (x != NULL)
{
cout << x->value;
x = x->forw[0];
if (x != NULL)
cout << " - ";
}
cout <<endl;
}

/*
* Search Elemets in Skip List
*/
bool skiplist::contains(int &s_value)
{
snode *x = header;
for (int i = level;i >= 0;i--)
{
while (x->forw[i] != NULL && x->forw[i]->value < s_value)
{
x = x->forw[i];
}
}
x = x->forw[0];
return x != NULL && x->value == s_value;
}
20. Write a C++ Program to Create a Graph using Adjacency Matrix Representation.

#include<iostream>
using namespace std;
int vertArr[20][20]; //the adjacency matrix initially 0
int count = 0;
void displayMatrix(int v) {
int i, j;
for(i = 0; i < v; i++) {
for(j = 0; j < v; j++) {
cout << vertArr[i][j] << " ";
}
cout << endl;
}
}
void add_edge(int u, int v) { //function to add edge into the matrix
vertArr[u][v] = 1;
vertArr[v][u] = 1;
}
main(int argc, char* argv[]) {
int v = 6; //there are 6 vertices in the graph
add_edge(0, 4);
add_edge(0, 3);
add_edge(1, 2);
add_edge(1, 4);
add_edge(1, 5);
add_edge(2, 3);
add_edge(2, 5);
add_edge(5, 3);
add_edge(5, 4);
displayMatrix(v);}
output:

21. Write a C++ program to implement graph traversal techniques

a) BFS
// Program to print BFS traversal from a given
// source vertex. BFS(int s) traverses vertices
// reachable from s.
#include<iostream>
#include <list>

using namespace std;

// This class represents a directed graph using

// adjacency list representation
class Graph
{
int V; // No. of vertices

// Pointer to an array containing adjacency

// lists
list<int> *adj;
public:
Graph(int V); // Constructor

// function to add an edge to graph

void addEdge(int v, int w);

// prints BFS traversal from a given source s

void BFS(int s);
};

Graph::Graph(int V)
{
this->V = V;
 adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)

{
adj*v+.push_back(w); // Add w to v’s list.
}

void Graph::BFS(int s)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;

// Create a queue for BFS

list<int> queue;

// Mark the current node as visited and enqueue it

visited[s] = true;
queue.push_back(s);

// 'i' will be used to get all adjacent

// vertices of a vertex
list<int>::iterator i;

while(!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
cout << s << " ";
queue.pop_front();

// Get all adjacent vertices of the dequeued

// vertex s. If a adjacent has not been visited,
// then mark it visited and enqueue it
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}

// Driver program to test methods of graph class

int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

cout << "Following is Breadth First Traversal "

<< "(starting from vertex 2) \n";
g.BFS(2);

return 0;
}
Output :

b) DFS
// C++ program to print DFS traversal from
// a given vertex in a given graph
#include <bits/stdc++.h>
using namespace std;

// Graph class represents a directed graph

// using adjacency list representation
class Graph {
public:
map<int, bool> visited;
map<int, list<int> > adj;

// function to add an edge to graph

void addEdge(int v, int w);

// DFS traversal of the vertices

// reachable from v
 void DFS(int v);
};

void Graph::addEdge(int v, int w)

{
adj[v].push_back(w); // Add w to v’s list.
}

void Graph::DFS(int v)
{
// Mark the current node as visited and
// print it
visited[v] = true;
cout << v << " ";

// Recur for all the vertices adjacent

// to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFS(*i);
}

// Driver code
int main()
{
// Create a graph given in the above diagram
Graph g;
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

cout << "Following is Depth First Traversal"

" (starting from vertex 2) \n";
g.DFS(2);

return 0;
}
Output :

22. Write a C++ program to Heap sort using tree structure.

// C++ program for implementation of Heap Sort

#include <iostream>
using namespace std;

// To heapify a subtree rooted with node i which is

// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2

// If left child is larger than root

if (l < n && arr[l] > arr[largest])
largest = l;

// If right child is larger than largest so far

if (r < n && arr[r] > arr[largest])
largest = r;

// If largest is not root

if (largest != i) {
swap(arr[i], arr[largest]);

// Recursively heapify the affected sub-tree

heapify(arr, n, largest);
}
}

// main function to do heap sort

void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
 // One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);

// call max heapify on the reduced heap

heapify(arr, i, 0);
}
}

/* A utility function to print array of size n */

void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}

// Driver program
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);

heapSort(arr, n);

cout << "Sorted array is \n";

printArray(arr, n);
}
Output: