Tree traversal and diameter

#include <iostream>
#include <string.h>
using namespace std;

int max(int p, int q)
{
 return ((p>q) ? p : q);
}

int max3(int p, int q, int r)
{
 return ((p>q) ? (p>r? p:r) : (q>r ? q:r));
}
class node;
class node
{
 public:
  char c;
  node* l;
  node* r;
};

void insert(node** root, char c)
{
 if(!(*root))
 {
  node* t = new node();
  t->c = c;
  t->l=NULL;
  t->r=NULL;
  *root = t;
  //cout << "root=" << (*root)->c << endl;
 }
 else
 {
  if((*root)->c > c)
  {
   if(!(*root)->l)
   {
    node* t = new node();
    t->c = c;
    t->l=NULL;
    t->r=NULL;
    (*root)->l = t;
    //cout << "left=" << (*root)->l->c << endl;
   }
   else
    insert(&((*root)->l), c);
  }
  else
  {
   if(!(*root)->r)
   {
    node* t = new node();
    t->c = c;
    t->l=NULL;
    t->r=NULL;
    (*root)->r = t;
    //cout << "right=" << (*root)->r->c << endl;
   }
   else
    insert(&((*root)->r), c);
  }
 }
}

void printinorder(node* root)
{
 if(!root)
 {
  return;
 }
 
 printinorder(root->l);
 cout << root->c << " ";
 printinorder(root->r);
}

int depth(node* root)
{
 if(!root)
  return 0;
 return 1 + max(depth(root->l), depth(root->r));
}

void printaltbylevel(node* root, int depth, int level)
{
 if(!root)
  return;
  
 if(depth == level)
 {
  cout << root->c;
 }
 else
 {
  if(depth%2 == 0)
  {
   printaltbylevel(root->l, depth, level+1);
   printaltbylevel(root->r, depth, level+1);
  }
  else
  {
   printaltbylevel(root->r, depth, level+1);
   printaltbylevel(root->l, depth, level+1);
  }
 }
}

void printbylevel(node* root, int depth, int level)
{
 if(!root)
  return;
  
 if(depth == level)
 {
  cout << root->c;
 }
 else
 {
  printbylevel(root->l, depth, level+1);
  cout<<"  ";
  printbylevel(root->r, depth, level+1);
 }
}

void printlevelorder(node *root)
{
 int d = depth(root);
 for(int i=0; i<d; i++)
 {
  for(int j=0;j<d-i;j++)
   cout << " ";
  printbylevel(root, i, 0);
  cout << endl;
 }
}

void printaltlevelorder(node *root)
{
 int d = depth(root);
 for(int i=0; i<d; i++)
 {
  printaltbylevel(root, i, 0);
 }
}

int diameter(node* root)
{
 if(!root)
  return 0;
  
 int lheight = depth(root->l);
 int rheight = depth(root->r);
 
 return (1 + max3(lheight + rheight, diameter(root->l), diameter(root->r)));
}
int main() {
 // your code goes here
 char s[100];
 cin >> s;
 node* root=NULL;
 for(int i=0; i<strlen(s);i++)
  insert(&root, s[i]);
 cout << "tree input is:" << s << endl;
 cout << "inorder: ";
 printinorder(root);
 cout << "\ntree depth=" << depth(root) << endl;
 cout << "level order: \n";
 printlevelorder(root);
 cout << "alt level order: \n";
 printaltlevelorder(root);
 cout << "\ndiameter of tree: " << diameter(root) <<endl;
 return 0;
}

tree input is:jfmcnabkd
inorder: a b c d f j k m n 
tree depth=5
level order: 
     j
    f  m
   c    k  n
  a  d          
   b              
alt level order: 
jmfckndab
diameter of tree: 7

palindrome substring of a given string

#include <iostream>
#include <string.h>
using namespace std;

bool ispalindrome(char* s, int l, int r)
{
 int n = r-l+1;
 for(int i=0; i<n/2; i++)
 {
  if(s[l+i] != s[r-i])
   return false;
 }
 
 for(int i=l; i<=r; i++)
  cout << s[i];
 cout << endl;
 return true;
}
void palindromesubstrings(char* s)
{
 int n = strlen(s);
 for(int i=0; i<n; i++)
 {
  for(int j=i+1; j<n; j++)
  {
   if(s[i] == s[j])
   {
    //cout << "[" << i << "," << j << "]=" << s[i] << endl;
    ispalindrome(s,i,j);
   }
  }
 }
}

int main() {
 // your code goes here
 char s1[100], s2[100];
 cin >> s1;
 cin >> s2;
 //cout << "palindrome " << s1 << " " << (ispalindrome(s1,0,strlen(s1)-1)? "true" : "false");
 cout << "palindrome substrings of " << s2 << ":\n";
 palindromesubstrings(s2);
 return 0;
}

palindrome substrings of ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD:
ABCBA
BCB
LL
OHO
RACECAR
ACECA
CEC
ARA
RAR
IAMAI
AMA
GG
OO

length of longest common subsequence of 2 strings

#include <iostream>
#include <string.h>
using namespace std;

/*

lcs(s1[1,m], s2[1,n]) = 1 + lcs(s1[1,m-1], s2[1,n-1]) 
       if s1[m] == s2[n]
 
 = max(lcs(s1[1,m-1], s2[1,n]) , lcs(s1[1,m], s2[1,n-1]) ) otherwise
*/
int max(int x, int y)
{
 return x>y?x:y; 
}
int lcs(char* s1, int m, char *s2, int n)
{
 if(m==0 || n==0)
  return 0;
  
 if(s1[m-1] == s2[n-1])
  return (1 + lcs(s1, m-1, s2, n-1));
  
 return max(lcs(s1, m-1, s2, n), lcs(s1, m, s2, n-1));
}

int lcsdp(char* s1, int m, char* s2, int n)
{
 int lcs[m+1][n+1];
 
 for(int i=0;i<=m; i++)
  for(int j=0; j<=n; j++)
   lcs[i][j] = 0;
 
 for(int i=1;i<=m; i++)
 {
  for(int j=1; j<=n; j++)
  {
   if(s1[i-1] == s2[j-1])
   {
    lcs[i][j] = 1 + lcs[i-1][j-1];
    //cout << s1[i-1] << " ";
   }
   else
   {
    lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j]);
    //cout << i << " " << j << " lcs:" << lcs[i][j] <<endl;
   }
  }
 }
 
 for(int i=0; i<=m; i++)
 {
  for(int j=0; j<=n;j++)
  {
   cout << lcs[i][j] << " ";
  }
  cout << endl;
 }
 return lcs[m][n];
}

int lcsdp2(char* s1, int m, char* s2, int n)
{
 int lcs[m+1][n+1];
 
 for(int i=0;i<=m; i++)
  for(int j=0; j<=n; j++)
   lcs[i][j] = 0;
 
 for(int i=1;i<=m; i++)
 {
  for(int j=1; j<=n; j++)
  {
   if(s1[i-1] == s2[j-1] & i!=j)
   {
    lcs[i][j] = 1 + lcs[i-1][j-1];
    //cout << i << " -" << j << " lcs:" << lcs[i][j] <<endl;
   }
   else
   {
    lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j]);
    //cout << i << " " << j << " lcs:" << lcs[i][j] <<endl;
   }
  }
 }
 
 for(int i=0; i<=m; i++)
 {
  for(int j=0; j<=n;j++)
  {
   cout << lcs[i][j] << " ";
  }
  cout << endl;
 }
 return lcs[m][n];
}

int main() {
 // your code goes here
 char s1[100], s2[100];
 cin >> s1;
 cin >> s2;
 cout << "length of longest increasing subsequence of "<<\
 s1 << " and " << s2 << " is: " << lcsdp(s1,strlen(s1),s2,strlen(s2));
 return 0;
}

input:
abba
acbfabc

output:
length of longest increasing subsequence of abba and acbfabc is: 3

edit distance of two strings

#include <iostream>
#include <string.h>
using namespace std;

int min(int x, int y, int z)
{
 return (x<y)?(x<z?x:z):(y<z?y:z);
}
/*

ed(s1[1,m], s2[1,n]) = ed(s1[1,m-1], s2[1,n-1]) if s1[m] == s2[n];
      = 1+ min( ed(s1[1-m-1], s2[1,n]),  remove  s1[m]
      ed(s1[1-m-1], s2[1,n-1])   replace s1[m] with s2[n]  
      ed(s1[1-m], s2[1,n-1]) )   insert s2[n] 
      if s1[m] != s2[n] 

*/
int editDistance(char* s1, int m, char* s2, int n)
{
 if(m==0)
  return n;
 if(n==0)
  return m;
  
 if(s1[m-1] == s2[n-1])
 {
  return editDistance(s1, m-1, s2, n-1);
 }
 return 1+ min(editDistance(s1,m-1, s2,n), \
 editDistance(s1, m-1, s2, n-1), editDistance(s1, m, s2, n-1));
}
int main() {
 // your code goes here
 char s1[] = "banana";
 char s2[] = "bana";
 char s3[] = "apple";
 char s4[] = "banaba";
 char s5[] = "bonanza";
 char s6[] = "banamf";
 
 cout << "edit of " << s1 << "-" << s2 << "=" \
 << editDistance(s1,strlen(s1), s2, strlen(s2)) << endl;
 cout << "edit of " << s1 << "-" << s3 << "=" \
 << editDistance(s1,strlen(s1), s3, strlen(s3)) << endl;
 cout << "edit of " << s1 << "-" << s4 << "=" \
 << editDistance(s1,strlen(s1), s4, strlen(s4)) << endl;
 cout << "edit of " << s1 << "-" << s5 << "=" \
 << editDistance(s1,strlen(s1), s5, strlen(s5)) << endl;
 cout << "edit of " << s1 << "-" << s6 << "=" \
 << editDistance(s1,strlen(s1), s6, strlen(s6)) << endl;
 return 0;
}

edit of banana-bana=2
edit of banana-apple=5
edit of banana-banaba=1
edit of banana-bonanza=2
edit of banana-banamf=2