3 SUM problem - O(n^2)

// Array is assumed to be sorted. If unsorted , sort it in O(nlogn)
// OUTPUT : -10 2 8

#include<stdio.h>

void threeSum(int arr[],int n){
int i=0;
int a,b,c,j,sum;
int k = n-1;
while(i<k-1){
a = arr[i];
c = arr[k];
for(j=i+1;j<k;j++){
b = arr[j];
sum = a+b+c;
if(sum == 0){
printf("%d %d %d",a,b,c);
return;
}
}
if(sum < 0){
i = i+1;
} else {
k = k-1;
}
}
}

int main(){
int arr[] = {-25,-10,-7,-3,2,4,8,10};
threeSum(arr,sizeof(arr)/sizeof(arr[0]));
return 0;
}

Printing N X N matrix in spiral order

// OUTPUT : 1 2 3 4 5 10 15 20 25 24 23 22 21 16 11 6 7 8 9 14 19 18 17 12 13

#include<stdio.h>
#define MAX 5

void printSpiral(int a[][MAX],int n){
int loop = (n+1)/2;
int i,j,k;
for(k=0;k<loop;k++){
i=k;
j=k;
for(j=k;j<MAX-1-k;j++){
printf("%d ",a[i][j]);
}
for(i=k;i<MAX-1-k;i++){
printf("%d ",a[i][j]);
}
for(j=MAX-1-k;j>k;j--){
printf("%d ",a[i][j]);
}
for(i=MAX-1-k;i>k;i--){
printf("%d ",a[i][j]);
}
}
if(loop%2){
printf("%d",a[loop-1][loop-1]);
}
}

int main(){
        int a[][MAX] = {{1,2,3,4,5},
                      {6,7,8,9,10},
                      {11,12,13,14,15},
                      {16,17,18,19,20},
     {21,22,23,24,25}};
printSpiral(a,MAX);
        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;
}

Inorder Traversal without using recursion

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

Preorder traversal of a BST, iteratively using a Stack

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

#define MAX 100

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

Node* s[MAX];
int top = -1;

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,1);
 insertNode(root,3);
 insertNode(root,6);
 insertNode(root,5);
 insertNode(root,7);
 *rootRef = root;
}

void push(Node* n){
s[++top] = n;
}

Node* pop(){
return s[top--];
}

int isempty(){
return (top==-1);
}

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

int main(){
 Node* root = NULL;
 createBST(&root);

 printf("\nPREORDER :\n");
 preorder(root);

 return 0;
}

Printing a N x N matrix using zigzag scanning algorithm

// Look here for zigzag scanning
// http://en.wikipedia.org/wiki/File:Zigzag_scanning.jpg
// INPUT : 4
// OUTPUT : 1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16

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

int populateMatrix(int *A,int n){
int i,j;
int k=1;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
*(A+i*n+j) = k++; 
}
}
}

void display(int *A,int n){
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
printf("%d ",*(A+n*i+j));
}
}
}

void goRight(int *A,int *i,int *j,int n){
int x = *i;
int y = *j;
printf("%d ",*(A+n*x+y));
*j = *j + 1;
}

void goDown(int *A,int *i,int *j, int n){
int x = *i;
int y = *j;
printf("%d ",*(A+n*x+y));
*i = *i + 1;
}

void goSW(int *A,int *i,int *j, int n){
int x = *i;
int y = *j;
while((y!=0) && (x!=n-1)){
printf("%d ",*(A+n*x+y));
x++;
y--;
}
*i = x;
*j = y;
}

void goNE(int *A,int *i,int *j, int n){
int x = *i;
int y = *j;
while((x!=0) && (y!=n-1)){
printf("%d ",*(A+n*x+y));
x--;
y++;
}
*i = x;
*j = y;
}

void goRightorDown(int *A,int *i,int *j,int n,int *prevrd){
if(*prevrd == 0){
goRight(A,i,j,n);
} else {
goDown(A,i,j,n);
}
*prevrd = !(*prevrd);
}

void goSWorNE(int *A,int *i,int *j,int n,int *prevsn){
if(*prevsn == 1){
goSW(A,i,j,n);
} else {
goNE(A,i,j,n);
}
*prevsn = !(*prevsn);
}

void zigzag(int *A,int n){
int i=0,j=0;
int prevrd = 0;
int prevsn = 1;
int k = 1;
int done = -1;
while(1 && n>1){
k=1;
while(1){
goRightorDown(A,&i,&j,n,&prevrd);
k++;
if(k==n){
done += 1;
break;
}
goSWorNE(A,&i,&j,n,&prevsn);
}
if(done){
break;
}
goSWorNE(A,&i,&j,n,&prevsn);
prevrd = !prevrd;
}
printf("%d ",*(A+n*i+j));
}

int main(){
int n;
scanf("%d",&n);
int *A = (int *)malloc(sizeof(int)*n*n);
populateMatrix(A,n);
zigzag(A,n);
free(A);
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;
}