Bca lab programs

1. Write Programs to implement the Stack operations using an array.

2. Write Programs to implement the Queue operations using an array.

3. Write Programs to implement the Stack operations using Linked lists

. 4. Write Programs to implement the Queue operations using Linked lists.

5. Write a program for postfix expression evaluation.

6. Write a program to convert prefix to postfix.

7. Write a program for Binary search Tree Traversals

8. Write a program to implement dequeue using a doubly linked list.

9. Write a program to search an item in a given list using

(i) LinearSearch

(ii) BinarySearch.

10. Write a program for

(i) BubbleSort

(ii) Quick Sort

(iii) Merge Sort.

AIM: Write a program to implement stack operations using array

ALOGRITHM:

Stack is a linear data structure which follows a particular order in which the operations are
performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
Mainly the following three basic operations are performed in the stack:
 Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow
condition.
 Pop: Removes an item from the stack. The items are popped in the reversed order in which
they are pushed. If the stack is empty, then it is said to be an Underflow condition.
 Peek or Top: Returns top element of stack.
 isEmpty: Returns true if stack is empty, else false.
Array implementation of Stack

In array implementation, the stack is formed by using the array. All the operations regarding the
stack are performed using arrays. Lets see how each operation can be implemented on the stack
using array data structure.

Adding an element onto the stack (push operation)

Adding an element into the top of the stack is referred to as push operation. Push operation
involves following two steps.

1. Increment the variable Top so that it can now refere to the next memory location.
2. Add element at the position of incremented top. This is referred to as adding new element
at the top of the stack.
Stack is overflow when we try to insert an element into a completely filled stack therefore, our
main function must always avoid stack overflow condition.

Algorithm:

begin

if top = n then stack full

top = top + 1

stack (top) : = item;

end
Deletion of an element from a stack (Pop operation)

Deletion of an element from the top of the stack is called pop operation. The value of the
variable top will be incremented by 1 whenever an item is deleted from the stack. The top most
element of the stack is stored in an another variable and then the top is decremented by 1. the
operation returns the deleted value that was stored in another variable as the result.

The underflow condition occurs when we try to delete an element from an already empty stack.

Algorithm:

begin

if top = 0 then stack empty;

item := stack(top);

top = top - 1;

end

Visiting each element of the stack (Peek operation)

Peek operation involves returning the element which is present at the top of the stack without
deleting it. Underflow condition can occur if we try to return the top element in an already empty
stack.

Algorithm :

PEEK (STACK, TOP)

begin
if top = -1 then stack empty

item = stack[top]

return item

end

PROGRAM:

#include<stdio.h>

int stack[100],choice,n,top,x,i;

void push(void);
void pop(void);

void display(void);

int main()

//clrscr();

top=-1;

printf("\n Enter the size of STACK[MAX=100]:");

scanf("%d",&n);

printf("\n\t STACK OPERATIONS USING ARRAY");

printf("\n\t--------------------------------");

printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");

do

printf("\n Enter the Choice:");

scanf("%d",&choice);

switch(choice)

case 1:

push();

break;

case 2:

pop();
 break;

case 3:

display();

break;

case 4:

printf("\n\t EXIT POINT ");

break;

default:

printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");

while(choice!=4);

return 0;

void push()

if(top>=n-1)
 {

printf("\n\tSTACK is over flow");

else

printf(" Enter a value to be pushed:");

scanf("%d",&x);

top++;

stack[top]=x;

void pop()

if(top<=-1)

printf("\n\t Stack is under flow");

else

printf("\n\t The popped elements is %d",stack[top]);

top--;

void display()
{

if(top>=0)

printf("\n The elements in STACK \n");

for(i=top; i>=0; i--)

printf("\n%d",stack[i]);

printf("\n Press Next Choice");

else

printf("\n The STACK is empty");

OUTPUT:

Enter the size of STACK[MAX=100]: 3

1.PUSH

2. POP

3.DISPLAY

4.EXIT

Enter the Choice:1

Enter a value to be pushed:12

Enter the Choice:1

Enter a value to be pushed:3

Enter the Choice:1

Enter a value to be pushed:23

Enter the Choice:1

STACK is over flow

Enter the Choice:2

The popped elements is 23

Enter the Choice:3

The elements in STACK

12

Press Next Choice

Enter the Choice:2

The popped elements is 3

Enter the Choice:2

The popped elements is 12

Enter the Choice:2

Stack is under flow

Enter the Choice:1

Enter a value to be pushed:12

Enter the Choice:3

The elements in STACK

12

Press Next Choice

Enter the Choice:4

EXIT POINT
AIM: Write a program to implement queue operations using array.

ALGORITHM:

Queue Operations using Array

Queue data structure using array can be implemented as follows...

Before we implement actual operations, first follow the below steps to create an empty queue.

 Step 1 - Include all the header files which are used in the program and define a
constant 'SIZE' with specific value.
 Step 2 - Declare all the user defined functions which are used in queue implementation.
 Step 3 - Create a one dimensional array with above defined SIZE (int queue[SIZE])
 Step 4 - Define two integer variables 'front' and 'rear' and initialize both with '-1'. (int
front = -1, rear = -1)
 Step 5 - Then implement main method by displaying menu of operations list and make
suitable function calls to perform operation selected by the user on queue.

enQueue(value) - Inserting value into the queue

In a queue data structure, enQueue() is a function used to insert a new element into the queue.
We can use the following steps to insert an element into the queue...

 Step 1 - Check whether queue is FULL. (rear == SIZE-1)

 Step 2 - If it is FULL, then display "Queue is FULL!!! Insertion is not
possible!!!" and terminate the function.
 Step 3 - If it is NOT FULL, then increment rear value by one (rear++) and
set queue[rear] = value.

deQueue() - Deleting a value from the Queue

In a queue data structure, deQueue() is a function used to delete an element from the queue. We
can use the following steps to delete an element from the queue...

 Step 1 - Check whether queue is EMPTY. (front == rear)

 Step 2 - If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not
possible!!!" and terminate the function.
 Step 3 - If it is NOT EMPTY, then increment the front value by one (front ++). Then
display queue[front] as deleted element. Then check whether both front and rear are
equal (front == rear), if it TRUE, then set both front and rear to '-1' (front = rear = -1)

display() - Displays the elements of a Queue

We can use the following steps to display the elements of a queue...

 Step 1 - Check whether queue is EMPTY. (front == rear)

 Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the
function.
 Step 3 - If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front+1'.
 Step 4 - Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same
until 'i' value reaches to rear (i <= rear)

PROGRAM:

#include <stdio.h>

#include<stdlib.h>

#define MAX 50

void insert();

void delete();

void display();

int queue_array[MAX];

int rear = - 1;

int front = - 1;

void main()

int choice;

while (1)

printf("1.Insert element to queue \n");

printf("2.Delete element from queue \n");

printf("3.Display all elements of queue \n");

printf("4.Quit \n");

printf("Enter your choice : ");

 scanf("%d", &choice);

switch (choice)

case 1:

insert();

break;

case 2:

delete();

break;

case 3:

display();

break;

case 4:

exit(0);

printf("\n\t EXIT POINT ");

break;

default:

printf("Wrong choice \n");

} /* End of switch */

} /* End of while */

} /* End of main() */

void insert()

{
 int add_item;

if (rear == MAX - 1)

printf("Queue Overflow \n");

else

if (front == - 1)

/*If queue is initially empty */

front = 0;

printf("Insert the element in queue : ");

scanf("%d", &add_item);

rear = rear + 1;

queue_array[rear] = add_item;

} /* End of insert() */

void delete()

if (front == - 1 || front > rear)

printf("Queue Underflow \n");

return ;

else

printf("Element deleted from queue is : %d\n", queue_array[front]);

front = front + 1;
 }

} /* End of delete() */

void display()

int i;

if (front == - 1)

printf("Queue is empty \n");

else

printf("Queue is : \n");

for (i = front; i <= rear; i++)

printf("%d ", queue_array[i]);

printf("\n");

OUTPUT:

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 1

Insert the element in queue : 12

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 1

Insert the element in queue : 45

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 34

Wrong choice

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 2

Element deleted from queue is : 12

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 2

Element deleted from queue is : 45

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit
Enter your choice :

Queue Underflow

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 3

Queue is :

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 1

Insert the element in queue :

34

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 1

Insert the element in queue : 12

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 3

Queue is :

34 12

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 4

QUIT

AIM: Write Programs to implement the Stack operations using Linked lists

ALGORITHM:

In linked list implementation of stack, the nodes are maintained non-contiguously in the
memory. Each node contains a pointer to its immediate successor node in the stack. Stack is said
to be overflown if the space left in the memory heap is not enough to create a node.

Push operation:

1. Create a node first and allocate memory to it.

2. If the list is empty then the item is to be pushed as the start node of the list. This includes
assigning value to the data part of the node and assign null to the address part of the node.
3. If there are some nodes in the list already, then we have to add the new element in the
beginning of the list (to not violate the property of the stack). For this purpose, assign the
address of the starting element to the address field of the new node and make the new
node, the starting node of the list.

Pop Operation:

Deleting a node from the top of stack is referred to as pop operation. Deleting a node
from the linked list implementation of stack is different from that in the array
implementation. In order to pop an element from the stack, we need to follow the
following steps :
 1. Check for the underflow condition: The underflow condition occurs when we
try to pop from an already empty stack. The stack will be empty if the head
pointer of the list points to null.
2. Adjust the head pointer accordingly: In stack, the elements are popped only
from one end, therefore, the value stored in the head pointer must be deleted and
the node must be freed. The next node of the head node now becomes the head
node

PROGRAM:
#include <stdio.h>
#include <stdlib.h>
void push();
void pop();
void display();
struct node
{
int val;
struct node *next;
};
int a;
struct node *head;
void main ()
{
int choice=0;
printf("\n*********Stack operations using linked list*********\n");
printf("\n----------------------------------------------\n");
while(choice != 4)
{
printf("\n\nChose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Display\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1: { push();
break;
}
case 2:
{
 pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
}
}
}
void push ()
{
int val;
struct node *ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("not able to push the element");
}
else
{
printf("Enter the value");
scanf("%d",&val);
if(head==NULL)
{
ptr->val = val;
ptr -> next = NULL;
head=ptr;
}
else
{
ptr->val = val;
 ptr->next = head;
head=ptr;

}
printf("Item pushed");

}
}

void pop()
{
int item;
struct node *ptr;
if (head == NULL)
{
printf("Underflow");
}
else
{
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped");

}
}
void display()
{
int i;
struct node *ptr;
ptr=head;
if(ptr == NULL)
{
printf("Stack is empty\n");
}
else
{
printf("Printing Stack elements \n");
while(ptr!=NULL)
{
 printf("%d->",ptr->val);
ptr = ptr->next;
if(ptr==NULL)
{
printf("NULL");
}
}
}
}

Output:

*********Stack operations using linked list*********

----------------------------------------------

Chose one from the below options...

1.Push

2.Pop

3.Display

4.Exit

Enter your choice

Enter the value12

Item pushed

Chose one from the below options...

1.Push

2.Pop

3.Display

4.Exit

Enter your choice

1
Enter the value45

Item pushed

Chose one from the below options...

1.Push

2.Pop

3.Display

4.Exit

Enter your choice

Enter the value67

Item pushed

Chose one from the below options...

1.Push

2.Pop

3.Display

4.Exit

Enter your choice

Printing Stack elements

67->45->12->NULL

Chose one from the below options...

1.Push

2.Pop

3.Display

4.Exit
Enter your choice

Item popped

Chose one from the below options...

1.Push

2.Pop

3.Display

4.Exit

Enter your choice

Printing Stack elements

45->12->NULL

Chose one from the below options...

1.Push

2.Pop

3.Display

4.Exit

Enter your choice

Item popped

Chose one from the below options...

1.Push

2.Pop

3.Display
4.Exit

Enter your choice

Item popped

Chose one from the below options...

1.Push

2.Pop

3.Display

4.Exit

Enter your choice

Underflow

Chose one from the below options...

1.Push

2.Pop

3.Display

4.Exit

Enter your choice

Stack is empty

Chose one from the below options...

1.Push

2.Pop

3.Display

4.Exit
Enter your choice

EXIT

Write Programs to implement the Queue operations using Linked lists.

In a linked queue, each node of the queue consists of two parts i.e. data part and the link
part. Each element of the queue points to its immediate next element in the memory.

In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear
pointer. The front pointer contains the address of the starting element of the queue while the rear
pointer contains the address of the last element of the queue.

Insertion and deletions are performed at rear and front end respectively. If front and rear both are
NULL, it indicates that the queue is empty.

Insert operation

The insert operation append the queue by adding an element to the end of the queue. The new
element will be the last element of the queue.

Firstly, allocate the memory for the new node ptr by using the following statement.

1. Ptr = (struct node *) malloc (sizeof(struct node));

There can be the two scenario of inserting this new node ptr into the linked queue.
In the first scenario, we insert element into an empty queue. In this case, the
condition front = NULL becomes true. Now, the new element will be added as the only
element of the queue and the next pointer of front and rear pointer both, will point to
NULL.

Algorithm
o Step 1: Allocate the space for the new node PTR
o Step 2: SET PTR -> DATA = VAL
o Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
 SET REAR -> NEXT = NULL
[END OF IF]
o Step 4: END

Deletion

Deletion operation removes the element that is first inserted among all the queue elements.
Firstly, we need to check either the list is empty or not. The condition front == NULL becomes
true if the list is empty, in this case , we simply write underflow on the console and make exit.

Otherwise, we will delete the element that is pointed by the pointer front. For this purpose, copy
the node pointed by the front pointer into the pointer ptr. Now, shift the front pointer, point to its
next node and free the node pointed by the node ptr. This is done by using the following
statements.

1. ptr = front;
2. front = front -> next;
3. free(ptr);

The algorithm and C function is given as follows.

Algorithm
o Step 1: IF FRONT = NULL
Write " Underflow "
Go to Step 5
[END OF IF]
o Step 2: SET PTR = FRONT
o Step 3: SET FRONT = FRONT -> NEXT
o Step 4: FREE PTR
o Step 5: END

PROGRAM:

#include<stdio.h>

#include<stdlib.h>
struct node

int data;

struct node *next;

};

struct node *front;

struct node *rear;

void insert();

void delete();

void display();

void main ()

int choice;

while(choice != 4)

printf("\n*************************Main Menu*****************************\
n");

printf("\
n=================================================================\n");

printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");

printf("\nEnter your choice ?");

scanf("%d",&choice);

switch(choice)

case 1:

insert();
 break;

case 2:

delete();

break;

case 3:

display();

break;

case 4:

exit(0);

break;

default:

printf("\nEnter valid choice??\n");

void insert()

struct node *ptr;

int item;

ptr = (struct node *) malloc (sizeof(struct node));

if(ptr == NULL)

printf("\nOVERFLOW\n");

return;
 }

else

printf("\nEnter value?\n");

scanf("%d",&item);

ptr -> data = item;

if(front == NULL)

front = ptr;

rear = ptr;

front -> next = NULL;

rear -> next = NULL;

printf("inserted element is: %d", item);

else

rear -> next = ptr;

rear = ptr;

rear->next = NULL;

printf("inserted element is: %d", item);

void delete ()

{
 struct node *ptr;

if(front == NULL)

printf("\nUNDERFLOW\n");

return;

else

ptr = front;

front = front -> next;

free(ptr);

printf("Element deleted");

void display()

struct node *ptr;

ptr = front;

if(front == NULL)

printf("\nEmpty queue\n");

else

{ printf("\nprinting values .....\n");

while(ptr != NULL)
 {

printf("\n%d\n",ptr -> data);

ptr = ptr -> next;

Output:

*************************Main Menu*****************************

=================================================================

1.insert an element

2.Delete an element

3.Display the queue

4.Exit

Enter your choice ?1

Enter value:

12

inserted element is: 12

*************************Main Menu*****************************

=================================================================

1.insert an element

2.Delete an element

3.Display the queue

4.Exit
Enter your choice ?1

Enter value:

12

inserted element is: 12

*************************Main Menu*****************************

=================================================================

1.insert an element

2.Delete an element

3.Display the queue

4.Exit

Enter your choice ?1

Enter value:

15

inserted element is: 15

*************************Main Menu*****************************

=================================================================

1.insert an element

2.Delete an element

3.Display the queue

4.Exit

Enter your choice ?3

printing values .....

12

12

15
*************************Main Menu*****************************

=================================================================

1.insert an element

2.Delete an element

3.Display the queue

4.Exit

Enter your choice ?4

Exit point

AIM: Write a program for postfix expression evaluation.

As Postfix expression is without parenthesis and can be evaluated as two operands and an
operator at a time, this becomes easier for the compiler and the computer to handle.

Evaluation rule of a Postfix Expression states:

1. While reading the expression from left to right, push the element in the stack if it is an
operand.
2. Pop the two operands from the stack, if the element is an operator and then evaluate it.
3. Push back the result of the evaluation. Repeat it till the end of the expression.

Algorithm

1) Add ) to postfix expression.

2) Read postfix expression Left to Right until ) encountered
3) If operand is encountered, push it onto Stack
[End If]
4) If operator is encountered, Pop two elements
i) A -> Top element
ii) B-> Next to Top element
iii) Evaluate B operator A
push B operator A onto Stack
5) Set result = pop
6) END

PROGRAM:

#incliude<stdio.h>
#include<stdio.h>
int stack[20];
int top = -1;

void push(int x)
{
stack[++top] = x;
}

int pop()
{
return stack[top--];
}

int main()
{
char exp[20];
char *e;
int n1,n2,n3,num;
clrscr();
printf("Enter the expression :: ");
scanf("%s",exp);
e = exp;
while(*e != '\0')
{
if(isdigit(*e))
{
num = *e - 48;
push(num);
}
else
{
n1 = pop();
n2 = pop();
switch(*e)
{
case '+':
{
n3 = n1 + n2;
break;
}
 case '-':
{
n3 = n2 - n1;
break;
}
case '*':
{
n3 = n1 * n2;
break;
}
case '/':
{
n3 = n2 / n1;
break;
}
}
push(n3);
}
e++;
}
printf("\nThe result of expression %s = %d\n\n",exp,pop());
getch();
return 0;
}
OUTPUT:
Enter the postfix Expr 123+*
Result is :5

AIM: Write a program to convert prefix to postfix.

Prefix: An expression is called the prefix expression if the operator appears in the expression
before the operands. Simply of the form (operator operand1 operand2).
Example : *+AB-CD (Infix : (A+B) * (C-D) )
Postfix: An expression is called the postfix expression if the operator appears in the expression
after the operands. Simply of the form (operand1 operand2 operator).
Example : AB+CD-* (Infix : (A+B * (C-D) )
Given a Prefix expression, convert it into a Postfix expression.
Conversion of Prefix expression directly to Postfix without going through the process of
converting them first to Infix and then to Postfix is much better in terms of computation and
better understanding the expression (Computers evaluate using Postfix expression).
Algorithm for Prefix to Postfix:
 Read the Prefix expression in reverse order (from right to left)
 If the symbol is an operand, then push it onto the Stack
 If the symbol is an operator, then pop two operands from the Stack
Create a string by concatenating the two operands and the operator after them.
string = operand1 + operand2 + operator
And push the resultant string back to Stack
 Repeat the above steps until end of Prefix expression.

PROGRAM:

#include<stdio.h>

#include<string.h>

void push(char item[],int *top, char s[][20])

*top=*top+1;

strcpy(s[*top],item);

void *pop(int *top,char s[][20])

char *item;

item=s[*top];

*top=*top-1;

return item;

void pre_post(char prefix[],char postfix[])

{
char s[20][20];

int top,i;

char symbol,temp[2];

char *op1,*op2;

top=-1;

strrev(prefix);

for(i=0;i<strlen(prefix);i++)

symbol=prefix[i];

temp[0]=symbol;

temp[1]='\0';

switch (symbol)

case '+':

case '-':

case '*':

case '/':

case '^':

op1=pop(&top,s);

op2=pop(&top,s);

strcpy(postfix,op1);
 strcat(postfix,op2);

strcat(postfix,temp);

push(postfix,&top,s);

break;

default:

push(temp,&top,s);

void main()

char prefix[20];

char postfix[20];

printf("\n\n Enter the prefix expression \n\n");

scanf("%s",prefix);

pre_post(prefix,postfix);

printf("\n\n The postfix expression is %s \n\n",postfix);

Output:
Enter the prefix expression

12+34*

The postfix expression is 43*

7. Write a program for Binary search Tree Traversals

The traversal operation plays a very important role while doing various other operations on the
data structure like some of the operations are searching, in which we need to visit each element
of the data structure at least once so that we can compare each incoming element from the data
structure to the key that we want to find in the data structure. So like any other data structure, the
tree data also needs to be traversed to access each element, also known as a node of the tree data
structure.

There are different ways of traversing a tree depending upon the order in which the tree's nodes
are visited and the types of data structure used for traversing the tree. There are various data
structures involved in traversing a tree, as traversing a tree involves iterating over all nodes in
some manner.

Types of Traversal of Binary Tree

There are three types of traversal of a binary tree.

1. Inorder tree traversal

2. Preorder tree traversal
3. Postorder tree traversal

Inorder Tree Traversal

The left subtree is visited first, followed by the root, and finally the right subtree in this traversal
strategy. Always keep in mind that any node might be a subtree in and of itself. The output of a
binary tree traversal in order produces sorted key values in ascending order.

Preorder Tree Traversal

In this traversal method, the root node is visited first, then the left subtree, and finally the right
subtree.

Postorder Tree Traversal

The root node is visited last in this traversal method, hence the name. First, we traverse the left
subtree, then the right subtree, and finally the root node.

PROGRAM:

#include <stdio.h>
#include <stdlib.h>
// Define the types of Traversals here
enum Traversal {PREORDER, INORDER, POSTORDER};

typedef enum Traversal Traversal;

typedef struct Node Node;

// Define the Tree Node here

struct Node {
int value;
// Pointers to the left and right children
Node* left, *right;
};

Node* init_tree(int data) {

// Creates the tree and returns the
// root node
Node* root = (Node*) malloc (sizeof(Node));
root->left = root->right = NULL;
root->value = data;
return root;
}

Node* create_node(int data) {

// Creates a new node
Node* node = (Node*) malloc (sizeof(Node));
node->value = data;
node->left = node->right = NULL;
return node;
}
void free_tree(Node* root) {
// Deallocates memory corresponding
// to every node in the tree.
Node* temp = root;
if (!temp)
return;
free_tree(temp->left);
free_tree(temp->right);
if (!temp->left && !temp->right) {
free(temp);
 return;
}
}

void print_tree(Traversal traversal, Node* root) {

// Prints the tree according to
// various types of traversals
if (!root)
return;
switch(traversal) {
case (PREORDER):
// Do a Preorder Traversal
printf("%d -> ", root->value);
print_tree(traversal, root->left);
print_tree(traversal, root->right);
break;

case (INORDER):
// Do an Inorder Traversal
print_tree(traversal, root->left);
printf("%d -> ", root->value);
print_tree(traversal, root->right);
break;

case (POSTORDER):
// Do a postorder Traversal
print_tree(traversal, root->left);
print_tree(traversal, root->right);
printf("%d -> ", root->value);
break;
}
}

int main() {
// Program to demonstrate finding the height of a Binary Tree

// Create the root node having a value of 10

Node* root = init_tree(10);

// Insert nodes onto the tree

 root->left = create_node(20);
root->right = create_node(30);

root->left->left = create_node(40);
root->left->right = create_node(50);

root->right->left = create_node(60);
root->right->right = create_node(70);

printf("----Preorder Traversal:----\n");
print_tree(PREORDER, root);
printf("\n\n");

printf("----Inorder Traversal:----\n");
print_tree(INORDER, root);
printf("\n\n");

printf("----Postorder Traversal:----\n");
print_tree(POSTORDER, root);
printf("\n\n");

// Free the tree!

free_tree(root);
return 0;
}

Output

----Preorder Traversal:----
10 -> 20 -> 40 -> 50 -> 30 -> 60 -> 70 ->

----Inorder Traversal:----
40 -> 20 -> 50 -> 10 -> 60 -> 30 -> 70 ->

----Postorder Traversal:----
40 -> 50 -> 20 -> 60 -> 70 -> 30 -> 10 ->

8. Write a program to implement dequeue using a doubly linked list.

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
class node
{
public:
int data;
class node *next;
class node *prev;
};
class dqueue: public node
{
node *head,*tail;
int top1,top2;
public:
dqueue()
{
top1=0;
top2=0;
head=NULL;
tail=NULL;
}
void push(int x)
{
node *temp;
int ch;
if(top1+top2 >=5)
{
cout <<"dqueue overflow";
return ;
}
if( top1+top2 == 0)
{
head = new node;
head->data=x;
head->next=NULL;
head->prev=NULL;
tail=head;
top1++;
}
else
 {
cout <<" Add element 1.FIRST 2.LAST\n Enter Your Choice:";
cin >> ch;
if(ch==1)
{
top1++;
temp=new node;
temp->data=x;
temp->next=head;
temp->prev=NULL;
head->prev=temp;
head=temp;
}
else
{
top2++;
temp=new node;
temp->data=x;
temp->next=NULL;
temp->prev=tail;
tail->next=temp;
tail=temp;
}
}
}
void pop()
{
int ch;
cout <<"Delete 1.First Node 2.Last Node\n Enter Your Choice:";
cin >>ch;
if(top1 + top2 <=0)
{
cout <<"\nDqueue under flow";
return;
}
if(ch==1)
{
head=head->next;
head->prev=NULL;
top1--;
}
 else
{
top2--;
tail=tail->prev;
tail->next=NULL;
}
}
void display()
{
int ch;
node *temp;
cout <<"Display From 1.STARTING 2.ENDING\n Enter Your Choice";
cin >>ch;
if(top1+top2 <=0)
{
cout <<"under flow";
return ;
}
if (ch==1)
{
temp=head;
while(temp!=NULL)
{
cout << temp->data <<" ";
temp=temp->next;
}
}
else
{
temp=tail;
while( temp!=NULL)
{
cout <<temp->data << " ";
temp=temp->prev;
}
}
}
};
int main()
{
dqueue d1;
 int ch;
while (1)
{
cout <<"1.INSERT 2.DELETE 3.DISPLAY 4.EXIT\n Enter Your Choice:";
cin >>ch;
switch(ch)
{
case 1:
cout <<"Enter the Element: ";
cin >> ch;
d1.push(ch);
break;
case 2:
d1.pop();
break;
case 3:
d1.display();
break;
case 4:
exit(1);
}
}<br> return 0;
}

OUTPUT:
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter Your Choice:1
Enter the Element: 10
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter ur choice:1
Enter the Element: 15
Add element 1.FIRST 2.LAST
Enter Your Choice:2
1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter Your Choice:3
Display From 1.STARTING 2.ENDING
Enter Your Choice:1
10 15 1.INSERT 2.DELETE 3.DISPLAY 4.EXIT
Enter Your Choice:4
9. Write a program to search an item in a given list using

(i) LinearSearch

ALGORITHM:

LINEAR_SEARCH(A, N, VAL)

Step 1: [INITIALIZE] SET POS = -1

Step 2: [INITIALIZE] SET I = 1

Step 3: Repeat Step 4 while I<=N

Step 4: IF A[I] = VAL

SET POS = I

PRINT POS

Go to Step 6

[END OF IF]

SET I = I + 1

[END OF LOOP]

Step 5: IF POS = -1

PRINT " VALUE IS NOT PRESENTIN THE ARRAY "

[END OF IF]

Step 6: EXIT

PROGRAM:
#include<stdio.h>

void main ()

int a[10] = {10, 23, 40, 1, 2, 0, 14, 13, 50, 9};

int item, i,flag;

clrscr();
printf(Elements in array are:\n”);

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

printf (“d\t”,a[i]);

printf("\nEnter Item which is to be searched\n");

scanf("%d",&item);

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

if(a[i] == item)

flag = i+1;

break;

else

flag = 0;

if(flag != 0)

printf("\nItem found at location %d\n",flag);

else

printf("\nItem not found\n");

getch();

}
 OUTPUT:

Enter number of elements of an array:

Enter elements:

2 3 57 8 6 4 1

Enter item to search:1

Item found at location 8

(ii) BinarySearch

ALGORITHM:

Step 1: [INITIALIZE] SET BEG = lower_bound

END = upper_bound, POS = - 1

Step 2: Repeat Steps 3 and 4 while BEG <=END

Step 3: SET MID = (BEG + END)/2

Step 4: IF A[MID] = VAL

SET POS = MID

PRINT POS

Go to Step 6

ELSE IF A[MID] > VAL

SET END = MID - 1

ELSE

SET BEG = MID + 1

[END OF IF]

[END OF LOOP]

Step 5: IF POS = -1

PRINT "VALUE IS NOT PRESENT IN THE ARRAY"

[END OF IF]

Step 6: EXIT

PROGRAM:

#include<stdio.h>

int binarySearch(int[], int, int, int);

void main ()

int arr[10] = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};

int item, location=-1;

clrscr();

printf("Enter the item which you want to search ");

scanf("%d",&item);

location = binarySearch(arr, 0, 9, item);

if(location != -1)

printf("Item found at location %d",location);

else

printf("Item not found");

getch();

int binarySearch(int a[], int beg, int end, int item)

{
 int mid;

if(end >= beg)

mid = (beg + end)/2;

if(a[mid] == item)

return mid+1;

else if(a[mid] < item)

return binarySearch(a,mid+1,end,item);

else

return binarySearch(a,beg,mid-1,item);

return -1;

OUTPUT:

Enter the item which you want to search

19

Item found at location 2

10. Write a program for

(i) BubbleSort

ALGORITHM :

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

Step 2: Repeat For J = i + 1 to N - I

Step 3: IF A[J] > A[i]

SWAP A[J] and A[i]

[END OF INNER LOOP]

[END OF OUTER LOOP

Step 4: EXIT

PROGRAM:

#include<stdio.h>

#include<stdio.h>

void main ()

int i, j,temp;

int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

clrscr();

printf(“Elements in array:\t);

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

printf("%d\t",a[i]);

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;

printf("Printing Sorted Element List ...\n");

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

printf("%d\n",a[i]);

getch();

OUTPUT:

Elements in array: 10 9 7 101 23 44 12 78 34 23

Printing Sorted Element List . . .

10

12

23

34

34

44
78

101

(ii) Quick Sort

ALGORITHM:

PARTITION (ARR, BEG, END, LOC)

Step 1: [INITIALIZE] SET LEFT = BEG, RIGHT = END, LOC = BEG, FLAG =

Step 2: Repeat Steps 3 to 6 while FLAG =

Step 3: Repeat while ARR[LOC] <=ARR[RIGHT]

AND LOC != RIGHT

SET RIGHT = RIGHT - 1

[END OF LOOP]

Step 4: IF LOC = RIGHT

SET FLAG = 1

ELSE IF ARR[LOC] > ARR[RIGHT]

SWAP ARR[LOC] with ARR[RIGHT]

SET LOC = RIGHT

[END OF IF]

Step 5: IF FLAG = 0

Repeat while ARR[LOC] >= ARR[LEFT] AND LOC != LEFT

SET LEFT = LEFT + 1

[END OF LOOP]

Step 6:IF LOC = LEFT

SET FLAG = 1

ELSE IF ARR[LOC] < ARR[LEFT]

SWAP ARR[LOC] with ARR[LEFT]

SET LOC = LEFT

[END OF IF]

[END OF IF]

Step 7: [END OF LOOP]

Step 8: END

QUICK_SORT (ARR, BEG, END)

Step 1: IF (BEG < END)

CALL PARTITION (ARR, BEG, END, LOC)

CALL QUICKSORT(ARR, BEG, LOC - 1)

CALL QUICKSORT(ARR, LOC + 1, END)

[END OF IF]

Step 2: END

PROGRAM: #include <stdio.h>

int partition(int a[], int beg, int end);

void quickSort(int a[], int beg, int end);

void main()

{
 int i;

int arr[10]={90,2,101,45,65,32,67,89,34,23};

clrscr();

quickSort(arr, 0, 9);

printf("\n The sorted array is: \n");

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

printf(" %d\t", arr[i]);

getch();

int partition(int a[], int beg, int end)

int left, right, temp, loc, flag;

loc = left = beg;

right = end;

flag = 0;

while(flag != 1)

while((a[loc] <= a[right]) && (loc!=right))

right--;

if(loc==right)

flag =1;
 else if(a[loc]>a[right])

temp = a[loc];

a[loc] = a[right];

a[right] = temp;

loc = right;

if(flag!=1)

while((a[loc] >= a[left]) && (loc!=left))

left++;

if(loc==left)

flag =1;

else if(a[loc] <a[left])

temp = a[loc];

a[loc] = a[left];

a[left] = temp;

loc = left;

}
 return loc;

void quickSort(int a[], int beg, int end)

int loc;

if(beg<end)

loc = partition(a, beg, end);

quickSort(a, beg, loc-1);

quickSort(a, loc+1, end);

} Output:

The Sorted array is: 2 23 32 34 45 65 67 89 90 101

(iii) Merge Sort.

#include<stdio.h>

#define max 10

Int a[11]={ 10,14,19,26,27,31,33,35,42,44,0};

Int b[10];

Void merging(int low, int mid, int high) {

Int 11, 12, I;

For(11=low,12=mid+1, i=low; 11<=mid &&12<=high; i++) {

If(a[11]<=a[12])
B[i]=a[11++];

Else

B[i]=a[12++];

While(11<=mid)

B[i++]=a[11++];

While(12<=high)

B[i++]=a[12++];

For(i=low; i<=high;i++)

A[i]=b[i];

Void sort(int low, int high) {

Int mid;

If(low<high) {

Mid=(low+high)/2;

Sort(low,mid);

Sort(mid+1,high);

Merging(low, midmhigh);

} else {

Return;

Int main() {

Int i;
Printf(“List before sorting\n”);

For(i=0;i<=max;i++)

Printf(“%d”,a[i]);

Sort(0,max);

Printf(“\nLast after sorting\n”);

For(i=0;i<max;i++)

Printf(“%d”,a[i]);

Output:

List before sorting

10 14 19 26 27 31 33 35 42 44 0

List after sorting

0 10 14 19 26 27 31 33 42 44