Program 1

Iterative C program to find length or count of nodes in a Linked list.

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* 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;
}
int getCount(struct Node* head)
{
int count = 0; // Initialize count
struct Node* current = head; // Initialize current
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
int main()
{
struct Node* head = NULL;
1->2->1->3->1 */
push(&head, 1);
push(&head, 3);
push(&head, 1);
push(&head, 2);
push(&head, 1);
printf("count of nodes is %d", getCount(head));
return 0;
}
Program 2
This program swaps the nodes of linked list rather than swapping the field
from the nodes.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void swapNodes(struct Node** head_ref, int x, int y){
if (x == y)
return;
struct Node *prevX = NULL, *currX = *head_ref;
while (currX && currX->data != x) {
prevX = currX;
currX = currX->next;
}
struct Node *prevY = NULL, *currY = *head_ref;
while (currY && currY->data != y) {
prevY = currY;
currY = currY->next;
}
if (currX == NULL || currY == NULL)
return;
if (prevX != NULL)
prevX->next = currY;
else
*head_ref = currY;
if (prevY != NULL)
prevY->next = currX;
else
*head_ref = currX;
struct Node* temp = currY->next;
currY->next = currX->next;
currX->next = temp;
}
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* start = NULL;
push(&start, 7);
push(&start, 6);
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);
printf("\n Linked list before calling swapNodes() ");
printList(start);
swapNodes(&start, 4, 3);
printf("\n Linked list after calling swapNodes() ");
printList(start);
return 0;
}
Program 3
Iterative C program to reverse a Linked list.

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
static void reverse(struct Node** head_ref){
struct Node* prev = NULL;
struct Node* current = *head_ref;
struct Node* next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
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* head){
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}
int main(){
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 85);
printf("Given linked list\n");
printList(head);
reverse(&head);
printf("\nReversed linked list \n");
printList(head);
getchar();
}
Program 4
C program to merge two sorted linked lists.
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void MoveNode(struct Node** destRef,
struct Node** sourceRef);
struct Node* SortedMerge(struct Node* a, struct Node* b)
{
struct Node dummy;
struct Node* tail = &dummy;
dummy.next = NULL;
while (1) {
if (a == NULL) {
tail->next = b;
break;
}
else if (b == NULL) {
tail->next = a;
break;
}
if (a->data <= b->data)
MoveNode(&(tail->next), &a);
else
MoveNode(&(tail->next), &b);
tail = tail->next;
}
return (dummy.next);
}
void MoveNode(struct Node** destRef,
struct Node** sourceRef){
struct Node* newNode = *sourceRef;
assert(newNode != NULL);
*sourceRef = newNode->next;
newNode->next = *destRef;
*destRef = newNode;
}
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* res = NULL;
struct Node* a = NULL;
struct Node* b = NULL;
push(&a, 15);
push(&a, 10);
push(&a, 5);
push(&b, 20);
push(&b, 3);
push(&b, 2);
res = SortedMerge(a, b);
printf("Merged Linked List is: \n");
printList(res);
return 0;
}
Program 5
C program for linked list merged sort.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* SortedMerge(struct Node* a, struct Node* b);
void FrontBackSplit(struct Node* source,
struct Node** frontRef, struct Node** backRef);
void MergeSort(struct Node** headRef)
{
struct Node* head = *headRef;
struct Node* a;
struct Node* b;
if ((head == NULL) || (head->next == NULL)) {
return;
}
FrontBackSplit(head, &a, &b);
MergeSort(&a);
MergeSort(&b);
*headRef = SortedMerge(a, b);
}
struct Node* SortedMerge(struct Node* a, struct Node* b)
{
struct Node* result = NULL;
if (a == NULL)
return (b);
else if (b == NULL)
return (a);
if (a->data <= b->data) {
result = a;
result->next = SortedMerge(a->next, b);
}
else {
result = b;
result->next = SortedMerge(a, b->next);
}
return (result);
}

void FrontBackSplit(struct Node* source,

struct Node** frontRef, struct Node** backRef)
{
struct Node* fast;
struct Node* slow;
slow = source;
fast = source->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->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;
}
int main()
{
struct Node* res = NULL;
struct Node* a = NULL;
push(&a, 15);
push(&a, 10);
push(&a, 5);
push(&a, 20);
push(&a, 3);
push(&a, 2);
MergeSort(&a);
printf("Sorted Linked List is: \n");
printList(a);
getchar();
return 0;
}
Program 6
C program to reverse a linked list in groups of given size
#include<stdio.h>
#include<stdlib.h>
struct Node{
int data;
struct Node* next;
};
struct Node *reverse (struct Node *head, int k)
{
if (!head)
return NULL;
struct Node* current = head;
struct Node* next = NULL;
struct Node* prev = NULL;
int count = 0;
while (current != NULL && count < k){
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
if (next != NULL)
head->next = reverse(next, k);
return prev;
}
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(void)
{
struct Node* head = NULL;
push(&head, 9);
push(&head, 8);
push(&head, 7);
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
printf("\nGiven linked list \n");
printList(head);
head = reverse(head, 3);
printf("\nReversed Linked list \n");
printList(head);
return(0);
}
Program 7
C Program to detect and remove loop.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int key;
struct Node* next;
} Node;
Node* newNode(int key){
Node* temp = (Node*)malloc(sizeof(Node));
temp->key = key;
temp->next = NULL;
return temp;
}
void printList(Node* head){
while (head != NULL) {
printf("%d ", head->key);
head = head->next;
}
printf("\n");
}
void detectAndRemoveLoop(Node* head){
if (head == NULL || head->next == NULL)
return;
Node *slow = head, *fast = head;
slow = slow->next;
fast = fast->next->next;
while (fast && fast->next) {
if (slow == fast)
break;
slow = slow->next;
fast = fast->next->next;
}
if (slow == fast) {
slow = head;
if (slow == fast)
while (fast->next != slow)
fast = fast->next;
else {
while (slow->next != fast->next) {
slow = slow->next;
fast = fast->next;
}
}
}
}
int main()
{
Node* head = newNode(50);
head->next = head;
head->next = newNode(20);
head->next->next = newNode(15);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(10);
head->next->next->next->next->next = head;
detectAndRemoveLoop(head);
printf("Linked List after removing loop \n");
printList(head);
return 0;
}
Program 8
C program to add two numbers represented by linked list.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
}Node;
Node* newNode(int data)d{
Node* new_node = (Node *)malloc(sizeof(Node));
new_node->data = data;
new_node->next = NULL;
return new_node;
}
void push(Node** head_ref, int new_data){
Node* new_node = newNode(new_data);
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
Node* addTwoLists(Node* first, Node* second){
Node* res = NULL;
Node *temp, *prev = NULL;
int carry = 0, sum;
while (first != NULL || second != NULL) {
sum = carry + (first ? first->data : 0) + (second ? second->data : 0);
carry = (sum >= 10) ? 1 : 0;
sum = sum % 10;
temp = newNode(sum);
if (res == NULL)
res = temp;
else
prev->next = temp;
prev = temp;
if (first)
first = first->next;
if (second)
second = second->next;
}
if (carry > 0)
temp->next = newNode(carry);
return res;
}
Node* reverse(Node* head)
{
if (head == NULL || head->next == NULL)
return head;
Node* rest = reverse(head->next);
head->next->next = head;
head->next = NULL;
return rest;
}
void printList(Node* node){
while (node != NULL) {
printf("%d ",node->data);
node = node->next;
}
printf("\n");
}
int main(void)
{
Node* res = NULL;
Node* first = NULL;
Node* second = NULL;
push(&first, 6);
push(&first, 4);
push(&first, 9);
push(&first, 5);
push(&first, 7);
printf("First list is ");
printList(first);
push(&second, 4);
push(&second, 8);
printf("Second list is ");
printList(second);
first = reverse(first);
second = reverse(second);
res = addTwoLists(first, second);
res = reverse(res);
printf("Resultant list is ");
printList(res);
return 0;
}
Program 9
C program to rotate a linked list counter clock wise.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void rotate(struct Node** head_ref, int k){
if (k == 0)
return;
struct Node* current = *head_ref;
int count = 1;
while (count < k && current != NULL) {
current = current->next;
count++;
}
if (current == NULL)
struct Node* kthNode = current;
while (current->next != NULL)
current = current->next;
current->next = *head_ref;
*head_ref = kthNode->next;
kthNode->next = NULL;
}
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(void){
struct Node* head = NULL;
for (int i = 60; i > 0; i -= 10)
push(&head, i);
printf("Given linked list \n");
printList(head);
rotate(&head, 4);
printf("\nRotated Linked list \n");
printList(head);
return (0);
}
Program 10
C Program for Generic Linked List.
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
void* data;
struct node* next;
} Node;
typedef struct list {
int size;
Node* head;
} List;
List* create_list() {
List* new_list = (List*)malloc(sizeof(List));
new_list->size = 0;
new_list->head = NULL;
return new_list;
}
void add_to_list(List* list, void* data) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = data;
new_node->next = list->head;

list->head = new_node;
list->size++;
}
void* remove_from_list(List* list) {
if (list->size == 0) {
return NULL;
}
Node* node_to_remove = list->head;
void* data = node_to_remove->data;
list->head = node_to_remove->next;
free(node_to_remove);
list->size--;
return data;
}
void free_list(List* list) {
Node* current_node = list->head;
while (current_node != NULL) {
Node* next_node = current_node->next;
free(current_node);
current_node = next_node;
}
free(list);
}

int main() {
List* int_list = create_list();
int x = 42;
add_to_list(int_list, (void*)&x);
int y = 13;
add_to_list(int_list, (void*)&y);
int z = 99;
add_to_list(int_list, (void*)&z);
int* int_ptr = NULL;
while ((int_ptr = (int*)remove_from_list(int_list)) != NULL) {
printf("%d\n", *int_ptr);
}
free_list(int_list);
return 0;
}
Program 11
C Program to convert infix to postfix expression
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_EXPR_SIZE 100
int precedence(char operator){
switch (operator) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
default:
return -1;
}
}
int isOperator(char ch){
return (ch == '+' || ch == '-' || ch == '*' || ch == '/'
|| ch == '^');
}
char* infixToPostfix(char* infix){
int i, j;
int len = strlen(infix);
char* postfix = (char*)malloc(sizeof(char) * (len + 2));
char stack[MAX_EXPR_SIZE];
int top = -1;
for (i = 0, j = 0; i < len; i++) {
if (infix[i] == ' ' || infix[i] == '\t')
continue;
if (isalnum(infix[i])) {
postfix[j++] = infix[i];
}
else if (infix[i] == '(') {
stack[++top] = infix[i];
}
else if (infix[i] == ')') {
while (top > -1 && stack[top] != '(')
postfix[j++] = stack[top--];
if (top > -1 && stack[top] != '(')
return "Invalid Expression";
else
top--;
}
else if (isOperator(infix[i])) {
while (top > -1
&& precedence(stack[top])
>= precedence(infix[i]))
postfix[j++] = stack[top--];
stack[++top] = infix[i];
}
}
while (top > -1) {
if (stack[top] == '(') {
return "Invalid Expression";
}
postfix[j++] = stack[top--];
}
postfix[j] = '\0';
return postfix;
}
int main(){
char infix[MAX_EXPR_SIZE] = "a+b*(c^d-e)^(f+g*h)-i";
char* postfix = infixToPostfix(infix);
printf("%s\n", postfix);
free(postfix);
return 0;
}
Program 12
C Program to Check for balance Bracket expression using Stack.
#include <stdio.h>
#include <stdlib.h>
#define bool int
struct sNode {
char data;
struct sNode* next;
};void push(struct sNode** top_ref, int new_data);
int pop(struct sNode** top_ref);
bool isMatchingPair(char character1, char character2){
if (character1 == '(' && character2 == ')')
return 1;
else if (character1 == '{' && character2 == '}')
return 1;
else if (character1 == '[' && character2 == ']')
return 1;
else
return 0;
}
bool areBracketsBalanced(char exp[])
{
int i = 0;
struct sNode* stack = NULL;
while (exp[i]) {
if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
push(&stack, exp[i]);
if (exp[i] == '}' || exp[i] == ')'
|| exp[i] == ']') {
if (stack == NULL)
return 0;
else if (!isMatchingPair(pop(&stack), exp[i]))
return 0;
}
i++;
}
if (stack == NULL)
return 1; // balanced
else
return 0; // not balanced
}
int main(){
char exp[100] = "{()}[]";
if (areBracketsBalanced(exp))
printf("Balanced \n");
else
printf("Not Balanced \n");
return 0;
}
void push(struct sNode** top_ref, int new_data)
{
struct sNode* new_node
= (struct sNode*)malloc(sizeof(struct sNode));
if (new_node == NULL) {
printf("Stack overflow n");
getchar();
exit(0);
}
new_node->data = new_data;
new_node->next = (*top_ref);
(*top_ref) = new_node;
}
int pop(struct sNode** top_ref){
char res;
struct sNode* top;
if (*top_ref == NULL) {
printf("Stack overflow n");
getchar();
exit(0);
}
else {
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}
Program 13
C program to evaluate value of a postfix expression.
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Stack {
int top;
unsigned capacity;
int* array;
};
struct Stack* createStack(unsigned capacity){
struct Stack* stack
= (struct Stack*)malloc(sizeof(struct Stack));
if (!stack)
return NULL;
stack->top = -1;
stack->capacity = capacity;
stack->array
= (int*)malloc(stack->capacity * sizeof(int));
if (!stack->array)
return NULL;
return stack;
}
int isEmpty(struct Stack* stack){
return stack->top == -1;
}
char peek(struct Stack* stack)
{
return stack->array[stack->top];
}
char pop(struct Stack* stack)
{
if (!isEmpty(stack))
return stack->array[stack->top--];
return '$';
}
void push(struct Stack* stack, char op)
{
stack->array[++stack->top] = op;
}
int evaluatePostfix(char* exp)
{
struct Stack* stack = createStack(strlen(exp));
int i;
if (!stack)
return -1;
for (i = 0; exp[i]; ++i) {
if (isdigit(exp[i]))
push(stack, exp[i] - '0');
else {
int val1 = pop(stack);
int val2 = pop(stack);
switch (exp[i]) {
case '+':
push(stack, val2 + val1);
break;
case '-':
push(stack, val2 - val1);
break;
case '*':
push(stack, val2 * val1);
break;
case '/':
push(stack, val2 / val1);
break;
}
}
}
return pop(stack);
}
int main(){
char exp[] = "231*+9-";
printf("postfix evaluation: %d", evaluatePostfix(exp));
return 0;
}
Program 14
C program to reverse a stack using recursion.
#include <stdio.h>
#include <stdlib.h>
#define bool int
struct sNode {
char data;
struct sNode* next;
};
void push(struct sNode** top_ref, int new_data);
int pop(struct sNode** top_ref);
bool isEmpty(struct sNode* top);
void print(struct sNode* top);
void insertAtBottom(struct sNode** top_ref, int item){
if (isEmpty(*top_ref))
push(top_ref, item);
else {
int temp = pop(top_ref);
insertAtBottom(top_ref, item);
push(top_ref, temp);
}
}
void reverse(struct sNode** top_ref){
if (!isEmpty(*top_ref)) {
int temp = pop(top_ref);
reverse(top_ref);
insertAtBottom(top_ref, temp);
}
}
int main(){
struct sNode* s = NULL;
push(&s, 4);
push(&s, 3);
push(&s, 2);
push(&s, 1);
printf("\n Original Stack ");
print(s);
reverse(&s);
printf("\n Reversed Stack ");
print(s);
return 0;
}
bool isEmpty(struct sNode* top){
return (top == NULL) ? 1 : 0;
}
void push(struct sNode** top_ref, int new_data){
struct sNode* new_node
= (struct sNode*)malloc(sizeof(struct sNode));
if (new_node == NULL) {
printf("Stack overflow \n");
exit(0);
}
new_node->data = new_data;
new_node->next = (*top_ref);
(*top_ref) = new_node;
}
int pop(struct sNode** top_ref){
char res;
struct sNode* top;
if (*top_ref == NULL) {
printf("Stack overflow \n");
exit(0);
}
else {
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}
void print(struct sNode* top){
printf("\n");
while (top != NULL) {
printf(" %d ", top->data);
top = top->next;
}
}
Program 15
C program to reverse a string using stack.
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Stack {
int top;
unsigned capacity;
char* array;
};
struct Stack* createStack(unsigned capacity){
struct Stack* stack
= (struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array
= (char*)malloc(stack->capacity * sizeof(char));
return stack;
}
int isFull(struct Stack* stack){
return stack->top == stack->capacity - 1;
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}
void push(struct Stack* stack, char item){
if (isFull(stack))
return;
stack->array[++stack->top] = item;
}
char pop(struct Stack* stack){
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top--];
}
void reverse(char str[]){
int n = strlen(str);
struct Stack* stack = createStack(n);
int i;
for (i = 0; i < n; i++)
push(stack, str[i]);
for (i = 0; i < n; i++)
str[i] = pop(stack);
}
int main(){
char str[] = "GeeksQuiz";
reverse(str);
printf("Reversed string is %s", str);
return 0;
}
Program 16
Implementation of BFS for graph using Adjacency list.
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 50
typedef struct Graph_t {
int V;
bool adj[MAX_VERTICES][MAX_VERTICES];
} Graph;
Graph* Graph_create(int V){
Graph* g = malloc(sizeof(Graph));
g->V = V;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
g->adj[i][j] = false;
}
}
return g;
}
void Graph_destroy(Graph* g) { free(g); }
void Graph_addEdge(Graph* g, int v, int w){
g->adj[v][w] = true;
}
void Graph_BFS(Graph* g, int s){
bool visited[MAX_VERTICES];
for (int i = 0; i < g->V; i++) {
visited[i] = false;
}
int queue[MAX_VERTICES];
int front = 0, rear = 0;
visited[s] = true;
queue[rear++] = s;
while (front != rear) {
s = queue[front++];
printf("%d ", s);
for (int adjacent = 0; adjacent < g->V;
adjacent++) {
if (g->adj[s][adjacent] && !visited[adjacent]) {
visited[adjacent] = true;
queue[rear++] = adjacent;
}
}
}
}
int main(){
Graph* g = Graph_create(4);
Graph_addEdge(g, 0, 1);
Graph_addEdge(g, 0, 2);
Graph_addEdge(g, 1, 2);
Graph_addEdge(g, 2, 0);
Graph_addEdge(g, 2, 3);
Graph_addEdge(g, 3, 3);
Printf(“following is Breadth First Traversal”
"(starting from vertex 2) \n");
Graph_BFS(g, 2);
Graph_destroy(g);
return 0;
}
Program 17
C program to check if Binary tree is sum tree or not.
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node* left;
struct node* right;
};
int isLeaf(struct node *node){
if(node == NULL)
return 0;
if(node->left == NULL && node->right == NULL)
return 1;
return 0;
}
int isSumTree(struct node* node){
int ls; // for sum of nodes in left subtree
int rs; // for sum of nodes in right subtree
return true */
if(node == NULL || isLeaf(node))
return 1;
if( isSumTree(node->left) && isSumTree(node->right)){
if(node->left == NULL)
ls = 0;
else if(isLeaf(node->left))
ls = node->left->data;
else
ls = 2*(node->left->data);
if(node->right == NULL)
rs = 0;
else if(isLeaf(node->right))
rs = node->right->data;
else
rs = 2*(node->right->data);
return(node->data == ls + rs);
}
return 0;
}
struct node* newNode(int data){
struct node* node =
(struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main(){
struct node *root = newNode(26);
root->left = newNode(10);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(6);
root->right->right = newNode(3);
if(isSumTree(root))
printf("The given tree is a SumTree ");
else
printf("The given tree is not a SumTree ");
getchar();
return 0;
}
Program 18
C program to check if two Nodes in a binary tree are cousins.
#include <stdio.h>
#include <stdlib.h>
struct Node{
int data;
struct Node *left, *right;
};
struct Node *newNode(int item){
struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
int isSibling(struct Node *root, struct Node *a, struct Node *b){
if (root==NULL) return 0;
return ((root->left==a && root->right==b)||
(root->left==b && root->right==a)||
isSibling(root->left, a, b)||
isSibling(root->right, a, b));
}
int level(struct Node *root, struct Node *ptr, int lev){
if (root == NULL) return 0;
if (root == ptr) return lev;

int l = level(root->left, ptr, lev+1);

if (l != 0) return l;
return level(root->right, ptr, lev+1);
}
int isCousin(struct Node *root, struct Node *a, struct Node *b){
if ((level(root,a,1) == level(root,b,1)) && !(isSibling(root,a,b)))
return 1;
else return 0;
}
int main(){
struct Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->right->right = newNode(15);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->left->right = newNode(8);
struct Node *Node1,*Node2;
Node1 = root->left->left;
Node2 = root->right->right;
isCousin(root,Node1,Node2)? puts("Yes"): puts("No");
return 0;
}
Program 19
Foldable Binary Trees by Changing Left Subtree to its mirror.
#include <stdio.h>
#include <stdlib.h>
#define bool int
#define true 1
#define false 0
struct node {
int data;
struct node* left;
struct node* right;
};
void mirror(struct node* node);
bool isStructSame(struct node* a, struct node* b);
bool isFoldable(struct node* root){
bool res;
if (root == NULL)
return true;
mirror(root->left);
res = isStructSame(root->left, root->right);
mirror(root->left);
return res;
}
bool isStructSame(struct node* a, struct node* b){
if (a == NULL && b == NULL) {
return true;
}
if (a != NULL && b != NULL
&& isStructSame(a->left, b->left)
&& isStructSame(a->right, b->right)) {
return true;
}
return false;
}
void mirror(struct node* node){
if (node == NULL)
return;
else {
struct node* temp;
mirror(node->left);
mirror(node->right);
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
struct node* newNode(int data){
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
int main(void){
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->right->left = newNode(4);
root->left->right = newNode(5);
if (isFoldable(root) == 1) {
printf("\n tree is foldable");
}
else {
printf("\n tree is not foldable");
}
getchar();
return 0;
}
Program 20
C Program to determine if given two trees are Identical or not.
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* left;
struct node* right;
};struct node* newNode(int data){
struct node* node= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
int identicalTrees(struct node* a, struct node* b){
if (a == NULL && b == NULL)
return 1;
if (a != NULL && b != NULL) {
return (a->data == b->data
&& identicalTrees(a->left, b->left)
&& identicalTrees(a->right, b->right));
}
return 0;}
int main(){
struct node* root1 = newNode(1);
struct node* root2 = newNode(1);
root1->left = newNode(2);
root1->right = newNode(3);
root1->left->left = newNode(4);
root1->left->right = newNode(5);
root2->left = newNode(2);
root2->right = newNode(3);
root2->left->left = newNode(4);
root2->left->right = newNode(5);
if (identicalTrees(root1, root2))
printf("Both tree are identical.");
else
printf("Trees are not identical.");
getchar();
return 0:
}
Program 21
Recursive optimized C program to find the diameter of a Binary Tree.
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *left, *right;
};
struct node* newNode(int data);
int max(int a, int b) { return (a > b) ? a : b; }
int height(struct node* node);
int diameter(struct node* tree){
if (tree == NULL)
return 0;
int lheight = height(tree->left);
int rheight = height(tree->right);
int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);
return max(lheight + rheight + 1,
max(ldiameter, rdiameter));
}
int height(struct node* node){
if (node == NULL)
return 0;
return 1 + max(height(node->left), height(node->right));
}
struct node* newNode(int data){
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
int main(){
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Diameter of the given binary tree is %d\n",diameter(root));
return 0;
}
Program 22
C Program to Get Level of a node in a Binary Tree.
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node* left;
struct node* right;
} node;
int getLevelUtil(node* node, int data, int level){
if (node == NULL)
return 0;
if (node->data == data)
return level;
int downlevel
= getLevelUtil(node->left, data, level + 1);
if (downlevel != 0)
downlevel = getLevelUtil(node->right, data, level + 1);
return downlevel;
}
int getLevel(node* node, int data){
return getLevelUtil(node, data, 1);
}
node* newNode(int data){
node* temp = (node*)malloc(sizeof(node));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
int main(){
node* root;
int x;
root = newNode(3);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(4);
for (x = 1; x <= 5; x++) {
int level = getLevel(root, x);
if (level)
printf(" Level of %d is %d\n", x,
getLevel(root, x));
else
printf(" %d is not present in tree \n", x);
}
getchar();
return 0;
}
Program 23
C program for Heap Sort.
#include <stdio.h>
#include<stdlib.h>
void swap(int* a, int* b){
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int N, int i){
int largest = i; int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < N && arr[left] > arr[largest])
largest = left;
if (right < N && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, N, largest);
}
}
void heapSort(int arr[], int N){
for (int i = N / 2 - 1; i >= 0; i--)
heapify(arr, N, i);
for (int i = N - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}
void printArray(int arr[], int N){
for (int i = 0; i < N; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main(){
int arr[] = { 12, 11, 13, 5, 6, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, N);
printf("Sorted array is\n");
printArray(arr, N);
}
Program 24
C Program to checks if a binary tree is max heap or not.
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
struct Node {
int key;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int k){
struct Node* node
= (struct Node*)malloc(sizeof(struct Node));
node->key = k;
node->right = node->left = NULL;
return node;
}
unsigned int countNodes(struct Node* root){
if (root == NULL)
return (0);
return (1 + countNodes(root->left)
+ countNodes(root->right));
}
bool isCompleteUtil(struct Node* root, unsigned int index, unsigned int number_nodes){
if (root == NULL)
return (true);
if (index >= number_nodes)
return (false);
return (isCompleteUtil(root->left, 2 * index + 1,
number_nodes)
&& isCompleteUtil(root->right, 2 * index + 2,
number_nodes));
}
bool isHeapUtil(struct Node* root){
if (root->left == NULL && root->right == NULL)
return (true);
if (root->right == NULL) {
return (root->key >= root->left->key);
}
else {
if (root->key >= root->left->key
&& root->key >= root->right->key)
return ((isHeapUtil(root->left))
&& (isHeapUtil(root->right)));
else
return (false);
}
}
bool isHeap(struct Node* root){
unsigned int node_count = countNodes(root);
unsigned int index = 0;
if (isCompleteUtil(root, index, node_count)
&& isHeapUtil(root))
return true;
return false;
}
int main(){
struct Node* root = NULL;
root = newNode(10);
root->left = newNode(9);
root->right = newNode(8);
root->left->left = newNode(7);
root->left->right = newNode(6);
root->right->left = newNode(5);
root->right->right = newNode(4);
root->left->left->left = newNode(3);
root->left->left->right = newNode(2);
root->left->right->left = newNode(1);
if (isHeap(root))
printf("Given binary tree is a Heap\n");
else
printf("Given binary tree is not a Heap\n");
return 0;
}
Program 25
C Program to Find whether an array is subset of another array.
#include <stdio.h>
#include<stdlib.h>
int isSubset(int arr1[], int arr2[], int m, int n){
int i = 0;
int j = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
if (arr2[i] == arr1[j])
break;
}
if (j == m)
return 0;
}
return 1;
}
int main(){
int arr1[] = { 11, 1, 13, 21, 3, 7 };
int arr2[] = { 11, 3, 7, 1 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
if (isSubset(arr1, arr2, m, n))
printf("arr2[] is subset of arr1[] ");
else
printf("arr2[] is not a subset of arr1[]");
getchar();
return 0;
}
Program 26
C Program for Implementation of BFS for Graph using Adjacency List.

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 50
typedef struct Graph_t {
int V;
bool adj[MAX_VERTICES][MAX_VERTICES];
} Graph;
Graph* Graph_create(int V){
Graph* g = malloc(sizeof(Graph));
g->V = V;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
g->adj[i][j] = false;
}
}
return g;
}
void Graph_destroy(Graph* g) { free(g); }void Graph_addEdge(Graph* g, int v, int w){
// Add w to v’s list.
g->adj[v][w] = true;
}
void Graph_BFS(Graph* g, int s){
bool visited[MAX_VERTICES];
for (int i = 0; i < g->V; i++) {
visited[i] = false;
}
int queue[MAX_VERTICES];
int front = 0, rear = 0;
visited[s] = true;
queue[rear++] = s;
while (front != rear) {
s = queue[front++];
printf("%d ", s);
for (int adjacent = 0; adjacent < g->V;
adjacent++) {
if (g->adj[s][adjacent] && !visited[adjacent]) {
visited[adjacent] = true;
queue[rear++] = adjacent;
}
}
}
}
int main(){
Graph* g = Graph_create(4);
Graph_addEdge(g, 0, 1);
Graph_addEdge(g, 0, 2);
Graph_addEdge(g, 1, 2);
Graph_addEdge(g, 2, 0);
Graph_addEdge(g, 2, 3);
Graph_addEdge(g, 3, 3);
printf("Following is Breadth First Traversal "
"(starting from vertex 2) \n");
Graph_BFS(g, 2);
Graph_destroy(g);
return 0;
}
Program 27
C Program for Depth First Search or DFS for a Graph.
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
struct Graph {
bool visited[MAX_VERTICES];
int adj[MAX_VERTICES][MAX_VERTICES];
};
void addEdge(struct Graph* graph, int v, int w) {
graph->adj[v][w] = 1;
}
void DFS(struct Graph* graph, int v) {
graph->visited[v] = true;
printf("%d ", v);
for (int i = 0; i < MAX_VERTICES; ++i) {
if (graph->adj[v][i] == 1 && !graph->visited[i]) {
DFS(graph, i);
}
}
}
int main() {
struct Graph graph;
int i, j;
for (i = 0; i < MAX_VERTICES; ++i) {
graph.visited[i] = false;
for (j = 0; j < MAX_VERTICES; ++j) {
graph.adj[i][j] = 0;
}
}
addEdge(&graph, 0, 1);
addEdge(&graph, 0, 2);
addEdge(&graph, 1, 2);
addEdge(&graph, 2, 0);
addEdge(&graph, 2, 3);
addEdge(&graph, 3, 3);
printf("Following is Depth First Traversal (starting from vertex 2)\n");
DFS(&graph, 2);
return 0;
}
Program 28
C Program to Print matrix in zig-zag fashion.
#include <stdio.h>
#include<stdlib.h>
void zigZagMatrix(int arr[][C], int n, int m){
int row = 0, col = 0;
int row_inc = 0;
int mn = (m < n) ? m : n;
for (int len = 1; len <= mn; ++len) {
for (int i = 0; i < len; ++i) {
printf("%d ", arr[row][col]);
if (i + 1 == len)
break;
if (row_inc)
++row, --col;
else
--row, ++col;
}
if (len == mn)
break;
if (row_inc)
++row, row_inc = 0;
else
++col, row_inc = 1;
}
if (row == 0) {
if (col == m - 1)
++row;
Else{
++col;
row_inc = 1;
}
}
else {
if (row == n - 1)
++col;
Else{
++row;
row_inc = 0;
}
}
int MAX = (m > n) ? m : n;
for (int len, diag = MAX - 1; diag > 0; --diag) {
if (diag > mn)
len = mn;
else
len = diag;
for (int i = 0; i < len; ++i) {
if (i + 1 == len)
break;
if (row_inc)
++row, --col;
else
++col, --row;
}
if (row == 0 || col == m - 1) {
if (col == m - 1)
++row;
else
++col;
row_inc = 1;
}
else if (col == 0 || row == n - 1) {
if (row == n - 1)
++col;
else
++row;
row_inc = 0;
}
}
}
int main(){
int matrix[][3] = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
zigZagMatrix(matrix, 3, 3);
return 0;
}
Program 29
C Program to find the scalar product of a matrix.
#include <stdio.h>
#include<stdlib.h>
void scalarProductMat(int mat[][N], int k){
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
mat[i][j] = mat[i][j] * k;
}
int main(){
int mat[N][N] = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
int k = 4;
scalarProductMat(mat, k);
printf("Scalar Product Matrix is : \n");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf("%d ", mat[i][j]);
printf("\n");
}
return 0;
}
Program 30
C Program to Delete a node in a Doubly Linked List.

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void deleteNode(struct Node** head_ref, struct Node* del){
if (*head_ref == NULL || del == NULL)
return;
if (*head_ref == del)*head_ref = del->next;
if (del->next != NULL)
del->next->prev = del->prev;
if (del->prev != NULL)
del->prev->next = del->next;
free(del);
return;
}
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->prev = NULL;
new_node->next = (*head_ref);
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
(*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, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
printf("\n Original Linked list ");
printList(head);
deleteNode(&head, head); /*delete first node*/
deleteNode(&head, head->next); /*delete middle node*/
deleteNode(&head, head->next); /*delete last node*/
printf("\n Modified Linked list ");
printList(head);
getchar();
}