Checking whether a tree is subset of another tree

bool identical(node * p,node * q)
{
if(p==NULL && q==NULL)
return true;
else if(p==NULL ||q==NULL)
return false;
else
return(p->data==q->data && identical(p->left,q->left) && identical(p->right,q->right));
}

bool subtree(node *p,node *q)
{
if(q==NULL)
return true;
else if(p==NULL)
return false;
else if(identical(p,q))
return true;
return subtree(p->left,q) || subtree(p->right,q);
}

Tree Traversal

PREORDER

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


INORDER

void inorder(node * root)
{

 if(root)
 {
  inorder(root->left);
  cout<<root->data;
  inorder(root->right);
 }

}


POSTORDER


void postorder(node * root)
{

 if(root)
 {
  postorder(root->left);
  postorder(root->right);
  cout<<root->data;
 }

}

Checking two trees are indentical

int identical(node* root1,node *root2)
{
if(!root1 && ! root2)
return 1;
else if((!root1 && root2) || (root1 &&!root2))
return 0;
else
return((root1==root2) && identical(root1->left,root2->left) && identical(root1->right,root2->right));
}

Finding minimum element in a Binary Search tree

RECURSIVE APPROACH

node * min(node * root)
{
if(!root)
return NULL;
else if(root->left==NULL)
return root;
else
min(root->left);
}

Counting number of elements in a tree

int count(node * root)
{
if(!root)
return 0;
else
return(1+count(root->left)+count(root->right));
}

Program to create mirror copy of a tree

node * mirror(node * head)
{
node * temp=new node();
if(head==NULL)
return NULL;
temp=head->data;
temp->left=mirror(head->right);
temp->right=mirror(head->left);
return temp;
}

Remove duplicates from a string

#include<iostream>
using namespace std;
bool chr[256]={0};
void rmdupli(char *a)
{
     int len=strlen(a);
     int i=0,j=0;
     while(i<len)
     {
             if(chr[a[i]]==0)
             {
             chr[a[i]]=1;
             a[j]=a[i];
             j++;
             }
             i++;
     }
     a[j]='\0';
     cout<<"\n The string is:"<<a;
}
int main()
{
    char str[] = "tinnytiny";
    rmdupli(str);
    system("pause");
    return 0;
}

Removing duplicates from a sorted array

#include<iostream>
using namespace std;
int rmduplicate(int a[],int n)
{
    int insert=1;
    for(int i=0;i<n;i++)
    {
            if(a[i]!=a[insert-1])
            {
            a[insert]=a[i];
            insert++;
            }
    }
    return insert;
}
int main()
{
    int a[]={1,1,1,2,2,3,3,3,3,3,4,4};
    int p=rmduplicate(a,12);
    for(int i=0;i<p;i++)
    cout<<a[i];
    system("pause");
    return 0;
}

TIME COMPLEXITY: O(n);

SPACE COMPLEXITY:O(1);

Check whether a string is rotation of other

eg-Like string response is a rotation of ponseres


void rotation(char *a,char *b)
{
int len=strlen(a);
int len2=strlen(b);
cout<<len<<len2;
if(len!=len2)
{
cout<<"\n Strings are not rotations of each other:";
}
else
{
char *c=new char(2*len);
strcpy(c,a);
cout<<"\n"<<c;
strcat(c,a);
cout<<c;
if(strstr(c,b))
cout<<"\n Strings are rotations of each other:";
else
cout<<"\n Strings are not rotations of each other:";
}
}

Checking whether two strings are anagrams of each other

void anagram(char *a,char *b)
{
int l1=strlen(a);
int l2=strlen(b);
int r;
if(l1!=l2)
{
cout<<"\n Strings are nor anagrams:";
}
else
{
for(int i=0;i<l1;i++)
r^=a[i]^b[i];
}
if(r==0)
cout<<"\n Strings are anagrams:";
else
cout<<"\n Strings are not anagrams:":
}

Reversing a doubly linked list

Reversing a doubly linked list is easier than reversing a singly linked list

struct node
{
int data;
node * next;
node * prev;
}
void reverse(node * head)
{
  node * pred=NULL,*succ;                          //successor and predecessor
  if(head==NULL)
     return;
  else
 {
   while(head)
   {
      succ=head->next;
      head->next=pred;
      head->prev=succ;
      pred=head;
      head=succ;
    }
 }
head=pred;
}

Reversing a singly linked list

Function to reverse a singly linked list

ITERATIVE APPROACH

void reverse(node * head)
{
node * prev=NULL,*tmp;
while(head)
{
tmp=head->next;
head->next=prev;
prev=head;
head=temp;
}
head=prev;
}

This will reverse a linked list in O(n) time complexity