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);
}
}
}

Buy and Sell Stocks

You have an array for which ith element is the price of a given stock on day i.
If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best time to buy and sell.

#include<stdio.h>

void maxProfit(int a[], int len){
int buy=0;
int sell=0;
int profit = 0;
int minSoFar = 0;
int i;
for(i=1;i<len;i++){
if(a[i] < a[minSoFar]){
minSoFar = i;
}
if(a[i] - a[minSoFar] > profit){
profit = a[i] - a[minSoFar];
buy = minSoFar;
sell = i;
}
}
printf("If you buy on day %d and sell on %d, you profit will be %d\n",buy,sell,profit);
}

int main(){
int a[] = {4,2,5,6,1,6,4};
maxProfit(a,sizeof(a)/sizeof(int));
return 0;
}

Inserting into Trie and Checking if an element is present in the Trie

// INPUT : char *str[] = { "one$", "two$", "three$", "four$", 
//                         "thre$" };
//         char *test[] = { "one$", "too$", "three$", "fore$" };
// OUTPUT : one$ is present, too$ is not present, three$ is 
//          present, fore$ is not present



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

#define ASIZE 255

typedef struct node {
    struct node *a[ASIZE];
} Node;

Node *newNode()
{
    Node *n = (Node *) malloc(sizeof(Node));
    int i;
    for (i = 0; i < ASIZE; i++) {
n->a[i] = NULL;
    }
    return n;
}

void insertTrie(Node ** rootRef, char *str)
{
    int len = strlen(str);
    int i;
    Node *root = *rootRef;
    if (root == NULL) {
root = newNode();
*rootRef = root;
    }
    for (i = 0; i < len; i++) {
int p = str[i];
if (root->a[p] == NULL) {
   root->a[p] = newNode();
}
root = root->a[p];
    }
}

int isPresent(Node * root, char *str)
{
    int len = strlen(str);
    int i;
    int isPresent = 1;
    for (i = 0; i < len; i++) {
int p = str[i];
if (root->a[p] == NULL) {
   isPresent = 0;
   break;
} else {
   root = root->a[p];
}
    }
    return isPresent;
}

printAllWordsRecur(Node *root,char *out,int len){
int i;
int done = 1;
for(i=0;i<ASIZE;i++){
if(root->a[i] == NULL){
continue;
} else{
done = 0;
out[len++] = i;
printAllWordsRecur(root->a[i],out,len);
len--;
}
}
if(done){
out[len] = '\0';
printf("%s\n",out);
}
}

printAllWords(Node *root){
static char out[50];
printAllWordsRecur(root,out,0);
}

int main()
{
    char *str[] = { "one$", "two$", "three$", "four$", "thre$" };
    char *test[] = { "one$", "too$", "three$", "fore$" };
    Node *root = NULL;
    int i;
    for (i = 0; i < 5; i++) {
insertTrie(&root, str[i]);
    }
    for (i = 0; i < 4; i++) {
if (isPresent(root, test[i])) {
   printf("%s is present\n", test[i]);
} else {
   printf("%s is not present\n", test[i]);
}
    }
    printAllWords(root);
    return 0;
}

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;
}

Remove duplicates from sorted array of integers (in place, no extra memory)

// INPUT : {1,1,1,2,2,2,2,2,2,3,3,3}
// OUTPUT : {1,2,3}

#include<stdio.h>

int main(){
int a[] = {1,1,1,2,2,2,2,2,2,3,3,3};
int i=0,j=0,n,k;
int len = sizeof(a)/sizeof(int);
while(1){
n = a[i];
while(a[j]==n && j<len){
j++;
}
if(j>=len){
break;
}
a[++i] = a[j];
}
for(k=0;k<=i;k++){
printf("%d ",a[k]);
}
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;
}

Push elements into stack. Pop should return the minimum element in the stack.

#include<iostream>

using namespace std;

class stack{
private:
int top;
int a[100];
public:
stack();
void push(int elem);
int pop();
void pushbubble(int elem);
bool isempty();
};

stack::stack(){
this->top = -1;
}

void stack::push(int elem){
a[++(this->top)] = elem;
}

void stack::pushbubble(int elem){
int temp;
if(!this->isempty()){
temp = this->pop();
if(temp > elem){
this->push(temp);
this->push(elem);
} else {
this->pushbubble(elem);
this->push(temp);
}
} else {
this->push(elem);
}
}

bool stack::isempty(){
return (this->top == -1);
}

int stack::pop(){
return a[(this->top)--];
}

int main(){
int a[] = {1,10,2,9,3,8,4,7,5,6};
stack s;
int i;
for(i=0;i<10;i++){
s.pushbubble(a[i]);
}
while(!s.isempty()){
cout<<s.pop()<<endl;
}
return 0;
}

Merge 2 Sorted Arrays (without using extra array)

// INPUT : int A[5] = {1,2,5,7,10};
// int B[12] = {0,3,4,6,8,9,13};
// OUTPUT : {0,1,2,3,4,5,6,7,8,9,10,13}

#include<stdio.h>

void mergeArray(int *A,int *B,int m,int n){
//A has m elements, B has n-m elements
int i=m-1,j=n-m-1,k=n-1;
while(i>=0 && j>=0){
if(A[i] > B[j]){
B[k--] = A[i--];
} else {
B[k--] = B[j--];
}
}
if(j<0){
while(i>=0){
B[k--] = A[i--];
}
}
}

int main(){
int A[5] = {1,2,5,7,10};
int B[12] = {0,3,4,6,8,9,13};
int sizeA = sizeof(A)/sizeof(int);
int sizeB = sizeof(B)/sizeof(int);
int i;
mergeArray(A,B,sizeA,sizeB);
for(i=0;i<sizeB;i++){
printf("%d ",B[i]);
}
return 0;
}

Delete all matching elements in the Linked List

// INPUT : 1->2->3->4->5
// OUTPUT : 2->3->4->5 for deleteNode(head,1);

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

typedef struct node{
 int data;
 struct node *next;
}Node;

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

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

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

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

Node* deleteNode(Node* head,int data){
Node* temp;
Node* n;
temp = head;
while(temp != NULL){
if(temp->data == data){
head = temp->next;
temp->next = NULL;
free(temp);
temp = head;
continue;
}
n = temp->next;
if(n != NULL && n->data == data){
temp->next = n->next;
n->next = NULL;
free(n);
continue;
}
if(n == NULL){
break;
} else {
temp = temp->next;
}
}
return head;
}

int main(){
 Node *head = NULL;
 buildList(&head);
 display(head);
 head = deleteNode(head,1);
 display(head);
 freeMem(head);
 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;
}