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