DS Tutorial 3
NAME – AKSHAY SURANGE
REG NO – 19MCA10049
1 Write a RemoveDuplicates () function which takes a doubly linked list and
deletes any duplicate nodes from the list.
#include<stdio.h>
#include<stdlib.h>
struct Node
int data;
struct Node* next;
};
void removeDuplicates(struct Node* head)
struct Node* current = head;
struct Node* next_next;
if (current == NULL)
return;
while (current->next != NULL)
if (current->data == current->next->data)
next_next = current->next->next;
free(current->next);
current->next = next_next;
else
current = current->next;
}
void push(struct Node** head_ref, int new_data)
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
void printList(struct Node *node)
while (node!=NULL)
printf("%d ", node->data);
node = node->next;
int main()
struct Node* head = NULL;
push(&head, 20);
push(&head, 13);
push(&head, 13);
push(&head, 11);
push(&head, 11);
push(&head, 11);
printf("\n Linked list before duplicate removal ");
printList(head);
removeDuplicates(head);
printf("\n Linked list after duplicate removal ");
printList(head);
return 0;
OUTPUT
2. Write a program for AVL Tree to implement the insertion operations: (For
nodes as integers) .Test the program for all cases (LL, RR, RL, LR rotation).
#include<stdio.h>
#include<stdlib.h>
struct Node
int key;
struct Node *left;
struct Node *right;
int height;
};
int max(int a, int b);
int height(struct Node *N)
if (N == NULL)
return 0;
return N->height;
int max(int a, int b)
return (a > b)? a : b;
}
struct Node* newNode(int key)
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return(node);
struct Node *rightRotate(struct Node *y)
struct Node *x = y->left;
struct Node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
return x;
struct Node *leftRotate(struct Node *x)
struct Node *y = x->right;
struct Node *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
return y;
int getBalance(struct Node *N)
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
struct Node* insert(struct Node* node, int key)
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
return node;
node->height = 1 + max(height(node->left),
height(node->right));
int balance = getBalance(node);
if (balance > 1 && key < node->left->key)
return rightRotate(node);
if (balance < -1 && key > node->right->key)
return leftRotate(node);
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
if (balance < -1 && key < node->right->key)
node->right = rightRotate(node->right);
return leftRotate(node);
return node;
void preOrder(struct Node *root)
if(root != NULL)
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
int main()
struct Node *root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
printf("Preorder traversal of the constructed AVL"
" tree is \n");
preOrder(root);
return 0;
}
OUTPUT
3. Given a graph G = (V, E) and |V| = n and |E| = m, where V is the set of
vertices and E is the set of edges. Write a program that will output the parent
node of each node in each of the following traversal mechanisms: a. Depth
First Traversal, b. Breadth First Traversal
import java.io.*;
import java.util.*;
class Graph
{
private int V;
private LinkedList<Integer> adj[];
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v,int w)
{
adj[v].add(w);
}
void BFS(int s)
{
boolean visited[] = new boolean[V];
LinkedList<Integer> queue = new LinkedList<Integer>();
queue.add(s);
while (queue.size() != 0)
{
s = queue.poll();
System.out.print(s+" ");
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext())
{
int n = i.next();
if (!visited[n])
{
visited[n] = true;
queue.add(n);
}
}
}
void DFS(int s) {
Vector<Boolean> visited = new Vector<Boolean>(V);
for (int i = 0; i < V; i++)
visited.add(false);
// Create a stack for DFS
Stack<Integer> stack = new Stack<>();
// Push the current source node
stack.push(s);
while(stack.empty() == false)
{
// Pop a vertex from stack and print it
s = stack.peek();
stack.pop();
// Stack may contain same vertex twice. So
// we need to print the popped item only
// if it is not visited.
if(visited.get(s) == false)
{
System.out.print(s + " ");
visited.set(s, true);
}
// Get all adjacent vertices of the popped vertex s
// If a adjacent has not been visited, then puah it
// to the stack.
Iterator<Integer> itr = adj[s].iterator();
while (itr.hasNext())
{
int v = itr.next();
if(!visited.get(v))
stack.push(v);
}
}
}
public static void main(String args[])
{
Graph g = new Graph(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);
System.out.println("Following is Breadth First Traversal "+
"(starting from vertex 2)");
g.BFS(2);
Graph g1 = new Graph(5);
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(1, 4);
System.out.println("\nFollowing is the Depth First Traversal");
g1.DFS(0);
}
}
OUTPUT
