Implementation of Heap Sort

#include<stdio.h>

#define LEFT(i) 2*i+1
#define RIGHT(i) 2*i+2

void maxHeapify(int a[],int p,int len){
int max = p;
int temp;
if(LEFT(p) < len && a[LEFT(p)] > a[p]){
max = LEFT(p);
}
if(RIGHT(p) < len && a[RIGHT(p)] > a[max]){
max = RIGHT(p);
}
if(max != p){
temp = a[max];
a[max] = a[p];
a[p] = temp;
maxHeapify(a,max,len);
}
}

void buildHeap(int a[],int len){
int i;
for(i=(len-2)/2;i>=0;i--){
maxHeapify(a,i,len);
}
}

void heapSort(int a[],int len){
buildHeap(a,len);
int i,temp;
int heapLen = len;
for(i=0;i<len;i++){
temp = a[0];
a[0] = a[heapLen-1];
a[heapLen-1] = temp;
heapLen--;
maxHeapify(a,0,heapLen);
}
}

void printSorted(int a[],int len){
int i;
for(i=0;i<len;i++){
printf("%d\t",a[i]);
}
}

int main(){
int a[] = {9,8,7,6,5,4,3,2,1};
int len = sizeof(a)/sizeof(a[0]);
heapSort(a,len);
printSorted(a,len);
return 0;
}

Rat in a maze - Backtracking method

#include<stdio.h>
#define ROW 4
#define COL 4

int findpath(int maze[ROW][COL],int path[ROW][COL],int i,int j){
static int found = 0;
if(i==ROW-1 && j==COL-1){
path[i][j] = 1;
found = 1;
return 1;
} else {
if(i<ROW && j<COL &&!found && (maze[i][j] == 1)){
path[i][j] = 1;
if(!findpath(maze,path,i+1,j) && !findpath(maze,path,i,j+1)){
path[i][j] = 0;
}
} else {
return 0;
}
}
}

int main(){
int maze[ROW][COL] = {{1,0,0,0},
                              {1,1,0,1},
                              {0,1,1,1},
                              {1,1,0,1}};
int path[ROW][COL] = {{0,0,0,0},
      {0,0,0,0},
      {0,0,0,0},
      {0,0,0,0}};
int i,j;
findpath(maze,path,0,0);
for(i=0;i<ROW;i++){
for(j=0;j<COL;j++){
printf("%d\t",path[i][j]);
}
printf("\n");
}
return 0;
}

Find an element in a sorted array which is rotated.

//INPUT : {6,7,8,0,1,2,3,4,5}
//OUTPUT : number found at index 7

#include<stdio.h>

int bsearch(int a[],int low,int high,int n){
if(high-low <=1){
if(a[low] == n) return low;
else if(a[high] == n) return high;
else return -1;
}
int mid = (low+high)/2;
if(a[mid] > a[low]){
if(n>=a[low] && n<=a[mid]){
return bsearch(a,low,mid,n);
} else {
return bsearch(a,mid+1,high,n);
}
} else {
if(n>=a[mid] && n<=a[high]){
return bsearch(a,mid,high,n);
} else {
return bsearch(a,low,mid-1,n);
}
}
}

int main(){
int a[] = {6,7,8,0,1,2,3,4,5};
int i = bsearch(a,0,sizeof(a)/sizeof(a[0])-1,4);
if(i==-1){
printf("number not found!!");
} else {
printf("number found at index %d",i);
}
return 0;
}

Convert Singly Linked List to height balanced BST

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
 int data;
 struct node *next;
 struct node *left;
}LNode;

LNode* newNode(int data){
 LNode *n = (LNode*)malloc(sizeof(LNode));
 n->data = data;
 n->next = NULL;
 n->left = NULL;
 return n;
}

void buildList(LNode **headRef){
 int i;
 for(i=7;i>0;i--){
  LNode *n = newNode(i);
  n->next = *headRef;
  *headRef = n;
 }
}

void freeMem(LNode *head){
    LNode *temp;
    while(head != NULL){
        temp = head;
        head = head->next;
        free(temp);
    }
}

void display(LNode *head){
 while(head->next != NULL){
  printf("%d->",head->data);
  head = head->next;
 }
 printf("%d\n",head->data);
}


LNode* buildBST(LNode* head){
        if(head == NULL || head->next == NULL) return head;
        LNode *root = NULL;
        LNode *slow = head;
        LNode *fast = head;
        LNode *prev = NULL;
        while(fast != NULL && fast->next != NULL){
                prev = slow;
                slow = slow->next;
                fast = fast->next->next;
        }

        root = slow;
        prev->next = NULL;
        root->left = buildBST(head);
        root->next = buildBST(slow->next);
        return root;
}

void preorder(LNode* root){
 if(root != NULL){
  printf("%d ",root->data);
  preorder(root->left);
  preorder(root->next);
 }
}

void inorder(LNode* root){
 if(root != NULL){
  inorder(root->left);
  printf("%d ",root->data);
  inorder(root->next);
 }
}

void postorder(LNode* root){
 if(root != NULL){
  postorder(root->left);
  postorder(root->next);
  printf("%d ",root->data);
 }
}

int main(){
 LNode *head = NULL;
 LNode *root = NULL;
 buildList(&head);
 display(head);
 root = buildBST(head);
 preorder(root);
 printf("\n");
 inorder(root);
 printf("\n");
 postorder(root);
// freeMem(head);
 return 0;
}

Sorted array is rotated. Find starting point or the index of the minimum element

// INPUT : {7,0,1,2,3,4,5,6}
// OUTPUT : array starts at value=0 and index=1

#include<stdio.h>

int findstartRecur(int a[],int start,int end){
int mid = (start+end)/2;
if(a[start] < a[end]){
return start;
}
if(end-start < 2){
return (a[end] < a[start])?end:start;
}
if(a[mid] > a[start]){
return findstartRecur(a,mid+1,end);
} else{
return findstartRecur(a,start,mid);
}
}

int main(){
int a[] = {7,0,1,2,3,4,5,6};
int start = findstartRecur(a,0,sizeof(a)/sizeof(int)-1);
printf("array starts at value=%d and index=%d",a[start],start);
return 0;
}

Print all permutations of a string

// INPUT : abc
// OUTPUT : abc,acb,bac,bca,cab,cba

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void strpermuteRecur(char *str,int *flag,int len,char *out,int n){
int i;
if(len == n){
out[len] = '\0';
printf("%s\n",out);
} else{
for(i=0;i<n;i++){
if(!flag[i]){
out[len++] = str[i];
flag[i] = 1;
strpermuteRecur(str,flag,len,out,n);
flag[i] = 0;
len--;
}
}
}
}

void strpermute(char *str){
static int *flag;
static char *out;
int i;
int n = strlen(str);
flag = (int *)malloc(sizeof(int)*n);
out = (char *)malloc(sizeof(char)*n);
for(i=0;i<n;i++){
flag[i] = 0;
}
strpermuteRecur(str,flag,0,out,n);
}

int main(){
char str[] = "abc";
strpermute(str);
return 0;
}

Print balanced parenthesis given n

// open - if open < n
// close - if close < n and close < open

#include<stdio.h>

void printparenthesisRecur(int n,int open,int close,char *str,int len){
if(len == 2*n){
str[len] = '\0';
printf("%s\n",str);
}
if(open < n){
str[len++] = '(';
printparenthesisRecur(n,open+1,close,str,len);
len--;
}
if(close < n && close < open){
str[len++] = ')';
printparenthesisRecur(n,open,close+1,str,len);
len--;
}
}

void printparenthesis(int n){
static char *str;
str = (char *)malloc(sizeof(char)*(2*n+1));
printparenthesisRecur(n,0,0,str,0);
}

int main(){
int n;
scanf("%d",&n);
printparenthesis(n);
return 0;
}

Checking if a tree is a valid BST and BST Recursive Traversals

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

typedef struct node{
int data;
struct node* left;
struct node* right;
}Node;

Node* newNode(int data){
Node* n = (Node *)malloc(sizeof(Node));
n->data = data;
n->left = NULL;
n->right = NULL;
return n;
}

void insertNode(Node* root,int data){
if(data < root->data){
if(root->left == NULL){
root->left = newNode(data);
} else {
insertNode(root->left,data);
}
} else {
if(root->right == NULL){
root->right = newNode(data);
} else {
insertNode(root->right,data);
}
}
}

Node* createBST(Node **rootRef){
Node *root = newNode(4);
insertNode(root,2);
insertNode(root,6);
insertNode(root,1);
insertNode(root,3);
insertNode(root,5);
insertNode(root,7);
*rootRef = root;
}

void inorder(Node* root){
if(root != NULL){
inorder(root->left);
printf("%d ",root->data);
inorder(root->right);
}
}

void preorder(Node* root){
if(root != NULL){
printf("%d ",root->data);
preorder(root->left);
preorder(root->right);
}
}

void postorder(Node* root){
if(root != NULL){
postorder(root->left);
postorder(root->right);
printf("%d ",root->data);
}
}

int isBSTRecur(Node* root,int min,int max){
if(root == NULL){
return 1;
}
if(root->data > min && root->data < max){
return (isBSTRecur(root->left,min,root->data) && isBSTRecur(root->right,root->data,max));
} else {
return 0;
}
}

int isBST(Node* root){
return isBSTRecur(root,INT_MIN,INT_MAX);
}

int main(){
Node* root = NULL;
createBST(&root);
printf("INORDER :\n");
inorder(root);
printf("\nPREORDER :\n");
preorder(root);
printf("\nPOSTORDER :\n");
postorder(root);
if(isBST(root)){
printf("Valid BST");
} else {
printf("Invalid BST");
}
return 0;
}