INDEX

Sr.No. Assignment name Page No. Date Sign

1
Polynomial Evaluation Using
Structure [with C++ program]

2 stack pop and push

3 C++ implementation to convert

infix expression to postfix
4 circular queue:

5 Bubble sort

6 Insertion Sort

7 Quick sort

8
Selection Sort

9
Quick sort

10 Linear search
11 Binary search implementation
12 Iterative implementation binary
tree
13 Singly linked list(linear)
14 Circular linked list
15 Binear search tree insertion
16 Check node exists or not in
binary tree
 Assignment no.1

Polynomial Evaluation Using Structure [with C++ program]

Polynomial Evaluation refers to finding the resultant of the polynomial expression for a particular value of polynomial
variable.
Example:P(x)= 4x3+6x2+7x+9 where x=2 then,
Result = 4(2)3+6(2)2+7(2)1+9 = 4(8)+6(4)+7(2)+9= 32+24+14+9= 79

Algorithm
Eval (struct poly p[10],int n,int x)

1.) [Initialize segment variables]

[Initialize Counter] Set i=0,sum=0

2.) Repeat step 3 while i<n

3.) sum=sum+p[i].coeff*pow(x,p[i].expo)

4.) Return sum;

5.) Exit

#include<iostream>

#include<math.h>

using namespace std;

/* declare structure for polynomial */

struct poly

int coeff;

int expo;

};

/* function prototypes */

int readPoly(struct poly []);

void displayPoly( struct poly [],int terms);

int eval(int n1,struct poly []);

int main()

int n1;

int value;

struct poly p1[20];

 cout<<"\n Enter the polynomial details:";

n1=readPoly(p1);

cout<<"\n The polynomial is: ";

displayPoly(p1,n1);

value=eval(n1,p1);

cout<<"\n The Resultant value of the polynomial is:"<<value<<endl;

return 0;

int readPoly(struct poly p[])

int t1,i;

cout<<"\n Enter the total number of terms in the polynomial: ";

cin>>t1;

cout<<"\n Enter the COEFFICIENT and EXPONENT "<<endl;

for(i=0;i<t1;i++)

cout<<" Enter the Coefficient("<<i+1<<"):";

cin>>p[i].coeff;

cout<<" Enter the Exponent("<<i+1<<"):";

cin>>p[i].expo;

return(t1);

void displayPoly(struct poly p[10],int term)

int k;

for(k=0;k<term-1;k++)

cout<<p[k].coeff<<"(x^"<<p[k].expo<<")+";

cout<<p[k].coeff<<"(x^"<<p[k].expo<<")";
}

int eval(int n1,struct poly p1[])

int i,sum,x;

cout<<"\n\n Enter the value of x for evaluation: ";

cin>>x;

sum=0;

for(i=0;i<n1;i++)

sum=sum + p1[i].coeff*pow(x,p1[i].expo);

return(sum);

Output
Enter the polynomial details:
Enter the total number of terms in the polynomial: 4

Enter the COEFFICIENT and EXPONENT

Enter the Coefficient(1):4
Enter the Exponent(1):3
Enter the Coefficient(2):6
Enter the Exponent(2):2
Enter the Coefficient(3):7
Enter the Exponent(3):1
Enter the Coefficient(4):9
Enter the Exponent(4):0

The polynomial is: 4(x^3)+6(x^2)+7(x^1)+9(x^0)

Enter the value of x for evaluation: 2

The Resultant value of the polynomial is:79
 Assignment 2

stack pop and push

// CPP program to demonstrate working of STL stack

#include <bits/stdc++.h>

using namespace std;

void showstack(stack <int> s)

while (!s.empty())

cout << '\t' << s.top();

s.pop();

cout << '\n';

int main ()

stack <int> s;

s.push(10);

s.push(30);

s.push(20);

s.push(5);

s.push(1);

cout << "The stack is : ";

showstack(s);

cout << "\ns.size() : " << s.size();

cout << "\ns.top() : " << s.top();

cout << "\ns.pop() : ";

s.pop();
 showstack(s);

return 0;

output:

the stack is 1 5 20 30 10

s.size(): 5

s.top():1

s.pop(): 5 20 30 10
 Assignment 3
/* C++ implementation to convert infix expression to postfix*/
// Note that here we use std::stack for Stack operations
#include<bits/stdc++.h>
using namespace std;

//Function to return precedence of operators

int prec(char c)
{
if(c == '^')
return 3;
else if(c == '*' || c == '/')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}

// The main function to convert infix expression

//to postfix expression
void infixToPostfix(string s)
{
std::stack<char> st;
st.push('N');
int l = s.length();
string ns;
for(int i = 0; i < l; i++)
{
// If the scanned character is an operand, add it to output string.
if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z'))
ns+=s[i];

// If the scanned character is an ‘(‘, push it to the stack.

else if(s[i] == '(')

st.push('(');

// If the scanned character is an ‘)’, pop and to output string from the stack
// until an ‘(‘ is encountered.
else if(s[i] == ')')
{
while(st.top() != 'N' && st.top() != '(')
{
char c = st.top();
st.pop();
ns += c;
}
if(st.top() == '(')
{
char c = st.top();
st.pop();
}
}

//If an operator is scanned

else{
while(st.top() != 'N' && prec(s[i]) <= prec(st.top()))
{
char c = st.top();
st.pop();
ns += c;
}
st.push(s[i]);
 }

}
//Pop all the remaining elements from the stack
while(st.top() != 'N')
{
char c = st.top();
st.pop();
ns += c;
}

cout << ns << endl;

//Driver program to test above functions

int main()
{
string exp = "a+b*(c^d-e)^(f+g*h)-i";
infixToPostfix(exp);
return 0;
}

output:
abcd^e-fgh*+^*+i-
 Assignment 4
Linear queue:
It is a linear data structure.
 It is considered as sequence of items.
 It supports FIFO (First In First Out) property.
 It has three components:
 A Container of items that contains elements of queue.
 A pointer front that points the first item of the queue.
 A pointer rear that points the last item of the queue.
 Insertion is performed from REAR end.
 Deletion is performed from FRONT end.
There are five operations possible on a queue:
1. Initialize operation
2. Addition or insertion operation.
3. Deletion operation.
4. Is_full check.
5. Is_empty check.
Algorithms:
In algorithm implementation first item of queue starts from 1, and in program implementation first
item will be start from 0.
1. INIT(QUEUE,FRONT,REAR)
2. INSERT-ITEM(QUEUE,FRONT,REAR,MAX,ITEM)
3. REMOVE-ITEM(QUEUE,FRONT,REAR,ITEM)
4. FULL-CHECK(QUEUE,FRONT,REAR,MAX,FULL)
5. EMPTY-CHECK(QUEUE,FRONT,REAR,EMPTY)
INIT(QUEUE,FRONT,REAR)
This algorithm is used to intialize a QUEUE,FRONT,
and REAR.
1. FRONT := 1;
2. REAR := 0;
3. Return;

INSERT-ITEM(QUEUE,FRONT,REAR,MAX,ITEM)
This algorithm is used to add or insert item to QUEUE.
1. If (REAR = MAX) then
a. Display “Queue overflow”;
b. Return;
2. Otherwise
a. REAR := REAR + 1;
b. QUEUE(REAR) := ITEM;
3. Return;

REMOVE-ITEM(QUEUE,FRONT,REAR,ITEM)
This algorithm is used to delete an item from QUEUE.
1. If (FRONT = REAR + 1) then
a. Display “Queue underflow”;
b. Return;
2. Otherwise
a. ITEM := QUEUE(FRONT);
b. FRONT := FRONT + 1;
3. Return;

EMPTY-CHECK(QUEUE,FRONT,REAR,EMPTY)
This algorithm is used to check whether
a QUEUE is EMPTY or not.
1. If (FRONT = REAR + 1) then
a. EMPTY := true;
2. Otherwise
a. EMPTY := false;
3. Return;
 FULL-CHECK(QUEUE,FRONT,REAR,MAX,FULL)
This algorithm is used to check whether
a QUEUE is full or not.
1. If ( REAR = MAX ) then
a. FULL := true;
2. Otherwise
a. FULL := false;
3. Return;

#include <iostream>
using namespace std;
#define MAX 5
class Queue
{
private:
int front,rear;
int ele[MAX];
public:
Queue() //To Initalize queue
{
front = 0;
rear = -1;
}

int isFull();
int isEmpty();
void insertQueue(int item);
int deleteQueue(int *item);
};

//To check queue is full or not

int Queue::isFull()
{
int full = 0 ;

if( rear == MAX-1 )

full = 1;

return full;
}

//To check queue is empty or not

int Queue::isEmpty()
{
int empty = 0 ;

if( front == rear + 1 )

empty = 1;

return empty;
}

//Insert Item into queue

void Queue:: insertQueue(int item)
{
if( isFull() )
{
cout<<"\nQueue OverFlow" << endl;
return;
}

ele[++rear]=item;
cout<<"\ninserted Value :" << item;
}

//delete item from queue

int Queue:: deleteQueue(int *item)
{
if( isEmpty() )
{
cout<<"\nQueue Underflow" << endl;
return -1;
}

*item = ele[front++];
return 0;
}

int main()
{
int item=0;
 Queue q = Queue();

q.insertQueue(10);
q.insertQueue(20);
q.insertQueue(30);
q.insertQueue(40);
q.insertQueue(50);
q.insertQueue(60);

if(q.deleteQueue( &item)==0)
cout<<"\nDeleted item : "<< item;

if(q.deleteQueue( &item)==0)
cout<<"\nDeleted item : "<< item;

if(q.deleteQueue( &item)==0)
cout<<"\nDeleted item : "<< item;

if(q.deleteQueue( &item)==0)
cout<<"\nDeleted item : "<< item;

if(q.deleteQueue( &item)==0)
cout<<"\nDeleted item : "<< item;

if(q.deleteQueue( &item)==0)
cout<<"\nDeleted item : "<< item;

cout<< endl;
return 0;
}
output:
inserted Value :10
inserted Value :20
inserted Value :30
inserted Value :40
inserted Value :50
Queue OverFlow

Deleted item : 10
Deleted item : 20
Deleted item : 30
Deleted item : 40
Deleted item : 50
Queue Underflow
 Assignment 5
circular queue:

Operations on Circular Queue:

 Front: Get the front item from queue.
 Rear: Get the last item from queue.
 enQueue(value) This function is used to insert an element into the circular queue. In a circular
queue, the new element is always inserted at Rear position.
Steps:
1. Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-
1)).
2. If it is full then display Queue is full. If queue is not full then, check if (rear == SIZE – 1
&& front != 0) if it is true then set rear=0 and insert element.
 deQueue() This function is used to delete an element from the circular queue. In a circular
queue, the element is always deleted from front position.

1. Algorithm Steps:
2. Check whether queue is Empty means check (front==-1).
3. If it is empty then display Queue is empty. If queue is not empty then step 3
4. Check if (front==rear) if it is true then set front=rear= -1 else check if (front==size-1), if
it is true then set front=0 and return the element.

// C or C++ program for insertion and

// deletion in Circular Queue
#include<bits/stdc++.h>
using namespace std;

struct Queue
{
// Initialize front and rear
int rear, front;

// Circular Queue
int size;
int *arr;

Queue(int s)
{
front = rear = -1;
size = s;
arr = new int[s];
}

void enQueue(int value);

 int deQueue();
void displayQueue();
};

/* Function to create Circular queue */

void Queue::enQueue(int value)
{
if ((front == 0 && rear == size-1) ||
(rear == (front-1)%(size-1)))
{
printf("\nQueue is Full");
return;
}

else if (front == -1) /* Insert First Element */

{
front = rear = 0;
arr[rear] = value;
}

else if (rear == size-1 && front != 0)

{
rear = 0;
arr[rear] = value;
}

else
{
rear++;
arr[rear] = value;
}
}

// Function to delete element from Circular Queue

int Queue::deQueue()
{
if (front == -1)
{
 printf("\nQueue is Empty");
return INT_MIN;
}

int data = arr[front];

arr[front] = -1;
if (front == rear)
{
front = -1;
rear = -1;
}
else if (front == size-1)
front = 0;
else
front++;

return data;
}

// Function displaying the elements

// of Circular Queue
void Queue::displayQueue()
{
if (front == -1)
{
printf("\nQueue is Empty");
return;
}
printf("\nElements in Circular Queue are: ");
if (rear >= front)
{
for (int i = front; i <= rear; i++)
printf("%d ",arr[i]);
}
else
{
for (int i = front; i < size; i++)
printf("%d ", arr[i]);
 for (int i = 0; i <= rear; i++)
printf("%d ", arr[i]);
}
}

/* Driver of the program */

int main()
{
Queue q(5);

// Inserting elements in Circular Queue

q.enQueue(14);
q.enQueue(22);
q.enQueue(13);
q.enQueue(-6);

// Display elements present in Circular Queue

q.displayQueue();

// Deleting elements from Circular Queue

printf("\nDeleted value = %d", q.deQueue());
printf("\nDeleted value = %d", q.deQueue());

q.displayQueue();

q.enQueue(9);
q.enQueue(20);
q.enQueue(5);

q.displayQueue();

q.enQueue(20);
return 0;
}
output:
Elements in Circular Queue are: 14 22 13 -6
Deleted value = 14
Deleted value = 22
Elements in Circular Queue are: 13 -6
Elements in Circular Queue are: 13 -6 9 20 5
Queue is Full
 Assignment 6

Bubble sort

Algorithm:

Step 1: For i = 0 to N-1 repeat Step 2

Step 2: For J = i + 1 to N – I repeat
Step 3: if A[J] > A[i]
Swap A[J] and A[i]
[End of Inner for loop]
[End if Outer for loop]
Step 4: Exit

Pseudocode:

Procedure bubble_sort (array , N)

array – list of items to be sorted
N – size of array
begin
swapped = false
repeat
for I = 1 to N-1
if array[i-1] > array[i] then
swap array[i-1] and array[i]
swapped = true
end if
end for
until not swapped
end procedure

#include<iostream>
using namespace std;
int main ()
{
int i, j,temp,pass=0;
int a[10] = {10,2,0,14,43,25,18,1,5,45};
cout <<"Input list ...\n";
for(i = 0; i<10; i++) {
cout <<a[i]<<"\t";
}
cout<<endl;
for(i = 0; i<10; i++) {
for(j = i+1; j<10; j++)
{
if(a[j] < a[i]) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
pass++;
}
cout <<"Sorted Element List ...\n";
for(i = 0; i<10; i++) {
cout <<a[i]<<"\t";
}
cout<<"\nNumber of passes taken to sort the list:"<<pass<<endl;
return 0;
}

output:

Input list …

10 2 0 14 43 25 18 1 5 45

Sorted Element List …

0 1 2 5 10 14 18 25 43 45

Number of passes taken to sort the list:10

 Assignment 7

Insertion Sort

Algorithm
// Sort an arr[] of size n
insertionSort(arr, n)
Loop from i = 1 to n-1.
……a) Pick element arr[i] and insert it into sorted sequence arr[0…i-1]

// C++ program for insertion sort

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

/* Function to sort an array using insertion sort*/

void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;

/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

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

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

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

insertionSort(arr, n);
printArray(arr, n);

return 0;
}

output:
5 6 11 12 13
 Assignment 8

Selection Sort
Algorithm:
arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]

// and place it at beginning
11 25 12 22 64

// Find the minimum element in arr[1...4]

// and place it at beginning of arr[1...4]
11 12 25 22 64

// Find the minimum element in arr[2...4]

// and place it at beginning of arr[2...4]
11 12 22 25 64

// Find the minimum element in arr[3...4]

// and place it at beginning of arr[3...4]
11 12 22 25 64

// C++ program for implementation of selection sort

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

void swap(int *xp, int *yp)

{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

void selectionSort(int arr[], int n)

{
int i, j, min_idx;

// One by one move boundary of unsorted subarray

for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
 // Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
}
}

/* Function to print an array */

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

// Driver program to test above functions

int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}

output:
Sorted array:
11 12 22 25 64
 Assignment 9
Quick sort

QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given
array around the picked pivot. There are many different versions of quickSort that pick pivot in
different ways.

Always pick first element as pivot.

Always pick last element as pivot (implemented below)
Pick a random element as pivot.
Pick median as pivot.

The key process in quickSort is partition(). Target of partitions is, given an array and an element x of
array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x)
before x, and put all greater elements (greater than x) after x. All this should be done in linear time.
Pseudo Code for recursive QuickSort function :

/* low --> Starting index, high --> Ending index */

quickSort(arr[], low, high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
pi = partition(arr, low, high);

quickSort(arr, low, pi - 1); // Before pi

quickSort(arr, pi + 1, high); // After pi
}
}

/* C++ implementation of QuickSort */

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

// A utility function to swap two elements

void swap(int* a, int* b)
{
 int t = *a;
*a = *b;
*b = t;
}

/* This function takes last element as pivot, places

the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high - 1; j++)

{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

/* The main function that implements QuickSort

arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
 // Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

/* Function to print an array */

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

// Driver Code
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}

output:
Sorted array:
1 5 7 8 9 10
 Assignment 10
Linear search
// C++ code to linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -1

#include <iostream>
using namespace std;

int search(int arr[], int n, int x)

{
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}

int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = search(arr, n, x);
(result == -1)? cout<<"Element is not present in array"
: cout<<"Element is present at index " <<result;
return 0;
}

output:
Element is present at index 3
 Assignment 11
Binary search
// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;

// A recursive binary search function. It returns

// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;

// If the element is present at the middle

// itself
if (arr[mid] == x)
return mid;

// If element is smaller than mid, then

// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);

// Else the element can only be present

// in right subarray
return binarySearch(arr, mid + 1, r, x);
}

// We reach here when element is not

// present in array
return -1;
}

int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
 int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}

output:
Element is present at index 3
 Assignment 12
Iterative implementation of Binary Search
// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;

// A iterative binary search function. It returns

// location of x in given array arr[l..r] if present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;

// Check if x is present at mid

if (arr[m] == x)
return m;

// If x greater, ignore left half

if (arr[m] < x)
l = m + 1;

// If x is smaller, ignore right half

else
r = m - 1;
}

// if we reach here, then element was

// not present
return -1;
}

int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
 (result == -1) ? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}

output:
Element is present at index 3
 Assignment 13
singly linked list(linear)
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *next;
};
struct Node* head = NULL;
void insert(int new_data) {
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = head;
head = new_node;
}
void display() {
struct Node* ptr;
ptr = head;
while (ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}
int main() {
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout<<"The linked list is: ";
display();
return 0;
}

output:
The linked list is: 9 2 7 1 3
 Assignment 14
circular linked list insertion

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

struct Node
{
int data;
struct Node *next;
};

struct Node *addToEmpty(struct Node *last, int data)

{
// This function is only for empty list
if (last != NULL)
return last;

// Creating a node dynamically.

struct Node *temp =
(struct Node*)malloc(sizeof(struct Node));

// Assigning the data.

temp -> data = data;
last = temp;

// Creating the link.

last -> next = last;

return last;
}

struct Node *addBegin(struct Node *last, int data)

{
if (last == NULL)
return addToEmpty(last, data);
 struct Node *temp =
(struct Node *)malloc(sizeof(struct Node));

temp -> data = data;

temp -> next = last -> next;
last -> next = temp;

return last;
}

struct Node *addEnd(struct Node *last, int data)

{
if (last == NULL)
return addToEmpty(last, data);

struct Node *temp =

(struct Node *)malloc(sizeof(struct Node));

temp -> data = data;

temp -> next = last -> next;
last -> next = temp;
last = temp;

return last;
}

struct Node *addAfter(struct Node *last, int data, int item)

{
if (last == NULL)
return NULL;

struct Node *temp, *p;

p = last -> next;
do
{
if (p ->data == item)
{
temp = (struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
 temp -> next = p -> next;
p -> next = temp;

if (p == last)
last = temp;
return last;
}
p = p -> next;
} while(p != last -> next);

cout << item << " not present in the list." << endl;
return last;

void traverse(struct Node *last)

{
struct Node *p;

// If list is empty, return.

if (last == NULL)
{
cout << "List is empty." << endl;
return;
}

// Pointing to first Node of the list.

p = last -> next;

// Traversing the list.

do
{
cout << p -> data << " ";
p = p -> next;

}
while(p != last->next);

}
// Driven Program
int main()
{
struct Node *last = NULL;

last = addToEmpty(last, 6);

last = addBegin(last, 4);
last = addBegin(last, 2);
last = addEnd(last, 8);
last = addEnd(last, 12);
last = addAfter(last, 10, 8);

traverse(last);

return 0;
}

output:
2 4 6 8 10 12
 Assignment 15
Binary serach tree
// C++ program to demonstrate insertion
// in a BST recursively.
#include <iostream>
using namespace std;

class BST
{
int data;
BST *left, *right;

public:

// Default constructor.
BST();

// Parameterized constructor.
BST(int);

// Insert function.
BST* Insert(BST *, int);

// Inorder traversal.
void Inorder(BST *);
};

// Default Constructor definition.

BST :: BST() : data(0), left(NULL), right(NULL){}

// Parameterized Constructor definition.

BST :: BST(int value)
{
data = value;
left = right = NULL;
}

// Insert function definition.

BST* BST :: Insert(BST *root, int value)
{
if(!root)
{
// Insert the first node, if root is NULL.
return new BST(value);
}

// Insert data.
if(value > root->data)
{
// Insert right node data, if the 'value'
// to be inserted is greater than 'root' node data.

// Process right nodes.

root->right = Insert(root->right, value);
}
else
{
// Insert left node data, if the 'value'
// to be inserted is greater than 'root' node data.

// Process left nodes.

root->left = Insert(root->left, value);
}

// Return 'root' node, after insertion.

return root;
}

// Inorder traversal function.

// This gives data in sorted order.
void BST :: Inorder(BST *root)
{
if(!root)
{
return;
}
Inorder(root->left);
 cout << root->data << endl;
Inorder(root->right);
}

// Driver code
int main()
{
BST b, *root = NULL;
root = b.Insert(root, 50);
b.Insert(root, 30);
b.Insert(root, 20);
b.Insert(root, 40);
b.Insert(root, 70);
b.Insert(root, 60);
b.Insert(root, 80);

b.Inorder(root);
return 0;
}

output:
20
30
40
50
60

70

80
 Assignment 16

// C++ program to check if a node exists

// in a binary tree
#include <iostream>
using namespace std;

// Binary tree node

struct Node {
int data;
struct Node *left, *right;
Node(int data)
{
this->data = data;
left = right = NULL;
}
};

// Function to traverse the tree in preorder

// and check if the given node exists in it
bool ifNodeExists(struct Node* node, int key)
{
if (node == NULL)
return false;

if (node->data == key)
return true;

/* then recur on left sutree */

bool res1 = ifNodeExists(node->left, key);

if(res1) return true; // node found, no need to look further

/* node is not found in left, so recur on right subtree */

bool res2 = ifNodeExists(node->right, key);

return res2;
}
// Driver Code
int main()
{
struct Node* root = new Node(0);
root->left = new Node(1);
root->left->left = new Node(3);
root->left->left->left = new Node(7);
root->left->right = new Node(4);
root->left->right->left = new Node(8);
root->left->right->right = new Node(9);
root->right = new Node(2);
root->right->left = new Node(5);
root->right->right = new Node(6);

int key = 4;

if (ifNodeExists(root, key))
cout << "YES";
else
cout << "NO";

return 0;
}

output:
YES