Constructing Binary Tree from In-Order and Pre-Order traversals - C++

/*
Binary Search Tree Implementation in C++
*/
#include<iostream>

using namespace std;

struct node{
char data;

node * left;
node * right;
} *root;


void printTree(node  * root){
if(root){
cout<<"(";
printTree(root->left);
cout<<root->data<<",";
printTree(root->right);
cout<<")";
}
}

int search(char A[], char key, int start, int end){
int pos = -1;
for(int i=start; i<= end; i++){
if(A[i] == key){
pos = i;
break;
}
}

return pos;
}

int preIndex = 0;
node * makeTree(char inOrder[], char preOrder[], int start, int end){
if(start > end){
return NULL;
}
node * temp = new node;
char key = preOrder[preIndex];
temp->data = key;
preIndex++;

if(start == end){
return temp;
}

int inIndex = search(inOrder, key, start, end);
if(inIndex == -1)
{
cout<<"Mismatch in preOrder and inOrder lists";
return NULL;
}

temp->left = makeTree(inOrder, preOrder, start, inIndex-1);
temp->right = makeTree(inOrder, preOrder, inIndex+1, end);
return temp;
}

int main(){
int n = 6;

char inOrder[] = {'D', 'B', 'E', 'A', 'F', 'C'};
char preOrder[] = {'A', 'B', 'D', 'E', 'C', 'F'};

root = makeTree(inOrder,preOrder,0,n-1);
printTree(root);

return 0;
}

Binary Search Tree implementation in C++

/*
Binary Search Tree Implementation in C++
*/
#include<iostream>

using namespace std;

struct node{
int data;

node * left;
node * right;
} *root;


node * insert(node *root, int e){
if(root == NULL){
root = new node;
root->data = e;
return root;
} else if ((root->data) > e) {
root->left = insert(root->left,e);
} else if ((root->data) < e) {
root->right = insert(root->right,e);
}

return root;

}

node * search(node * root, int e){
if(root == NULL){
return NULL;
} else if(root->data == e){
return root;
} else if(root->data > e){
return search(root->left,e);
} else {
return search(root->right,e);
}
}

void makeTreeFromArray(int A[], int n){
for(int i=0; i<n;i++){
root = insert(root, A[i]);
}
}

void printTree(node  * root){
if(root){
//cout<<"(";
printTree(root->left);
cout<<root->data<<"  ";
printTree(root->right);
//cout<<")";
}
}

int countLeaves(node * root){
if(root == NULL){
return 0;
} else {
if( (root->left == NULL) && (root->right == NULL) ){
return 1;
} else {
return countLeaves(root->left) + countLeaves(root->right);
}
}
}
node * findMax(node * root){
if(root == NULL){
return NULL;
} else if(root->right == NULL){
return root;
} else {
return findMax(root->right);
}
}

node * deleteNode(node * root, int e){
if(root == NULL){
cout<<"Element not found";
} else if(e > root->data){
root->right = deleteNode(root->right, e);
} else if(e < root->data){
root->left = deleteNode(root->left, e);
} else {
if(root->left && root->right){
node * temp = findMax(root->left);
root->data = temp->data;
root->left = deleteNode(root->left, temp->data);
} else {
node * temp = root;
if(root->left){
root = root->left;
}else if(root->right){
root = root-> right;
} else {
root = NULL;
}
delete temp;
}
}
return root;
}



int main(){
int A[] = {6,2,10,1,3,8,11,7,9,5,4};
int n = 11;

makeTreeFromArray(A,n);
printTree(root);

cout<<"\n";

root = deleteNode(root, 6);
printTree(root);
cout<<"\nNumber of leaves : "<<countLeaves(root)<<"\n";
return 0;
}

KMP String Matching in C++

/*
 Program to match a pattern in a given string using KMP Algorithm
 Run time of the Algo : O(n + m)
  n - Size of String
  m - Size of Pattern
 @author - yazar : yazar.y@gmail.com
*/
#include <iostream>
#include<cstring>

using namespace std;

//Variable to strore the prefix function
//If there is a mismatch between T[i] and P[j] then we will look into 
//F[j-1] to get the next potential match location
int F[200];

//Function to compute Prefix function for the given pattern
void createPrefixTable(char P[], int m){
 int i = 1;
 int j = 0;
 //If there is a mismatch in the 0th location of pattern, 
 //it is then good to look again at 0th position for a match
 F[0] = 0;
 
 //Loop to set each field of prefix table
 while(i<m){
  //If ith location in prefix table matches that of jth location
  //then set the next location to be matched in case of failure as 
  //j+1
  if(P[i] == P[j]){
   F[i] = j+1;
   i++;
   j++;
  } else if(j>0){
   //If there is a mismatch while computing the 

   //match prefix with the pattern,
   // Set the value of j to next potential point of match
   j = F[j-1];
  } else {
   F[i] = 0;
   i++;
  }
 
 }
}

//Function to match a pattern within a text
int matchPattern(char T[], int n, char P[], int m){
 //Computing prefix table for matching
 createPrefixTable(P,m);
 int i=0, j=0;
 
 //Loop to iterate throughout the text
 while(i<n){
  //If there is a match in the current character within the pattern
  if(T[i] == P[j]){
   //If the entire pattern is matched, return current location
   if(j == (m-1) ){
    return i - j;
   } else {
    //Otherwise increment i and j, so that 

    //consecutive Pattern positions will be matched
    i++;
    j++;
   }
  } else if(j > 0){
   //If there is a mismatch, set the value 

   //of j to next potential point of Match
   //(ie. F[j-1] as there is a match till P[j-1])
   j = F[j-1];
  } else {
   i++;
  }
 }
 
 return -1;
} 

int main(){
 char P[200], T[500];
 
 //Readin the Text and pattern from user
 cout<<"Enter a pattern : ";
 cin>>P;
 
 cout<<"Enter a String : ";
 cin>>T;
 int n, m;
 
 n = strlen(T);
 m = strlen(P);
 
 //Calling the function to perform match
 int location = matchPattern(T,n,P,m);
 
 if(location == -1){
  cout<<"Pattern "<<P<<" Not found in String "<<T<<"\n";
 } else {
  cout<<"Pattern "<<P<<" found in the string "<<T<<" at "<<location<<"\n";
 }
 return(0);
}