Lowest common Ancestor in tree

#include <iostream>
using namespace std;

struct node
{
int data;
node *left;
node *right;
};

void printTree(node *t){
if(t){
cout<<t->data<<" ";
printTree(t->left);
printTree(t->right);
}
}
node *getNode(int d){

node *temp = new node;
temp->data = d;
temp->left=temp->right = NULL;
return temp;
}
bool isPresent(node *t,int a)
{
if(t!=NULL){
if(t->data==a||isPresent(t->left,a)||isPresent(t->right,a))
return true;
}
return false;
}
node *commonAncestor(node *t,int a,int b)
{
static int count =0;
if(t!=NULL)
{
if((isPresent(t->left,a)&&isPresent(t->right,b))||(isPresent(t->right,a)&&isPresent(t->left,b)))
return t;
node *p= commonAncestor(t->left,a,b);

if(p)
return p;
else
return commonAncestor(t->right,a,b);
}
return NULL;
}
int main (){

node *t = getNode(5);
t->left= getNode(2);
t->right= getNode(7);
t->left->left= getNode(12);
t->right->right= getNode(17);
t->left->right= getNode(21);
t->right->left= getNode(71);
printTree(t);
node *p = commonAncestor(t,71,17);
if(p==NULL)
cout<<"NO common Ancestor";
else
cout<<"common ancestor is "<<p->data;
}

Heapsort in Python

def parent(i):
return i/2

def  left(i):
return 2*i

def  right(i):
return 2*i+1


def heapify(A,i,n):
l=left(i)
r=right(i)
largest=i
if l<=n and A[l]>A[largest]:
largest=l
if r<=n and A[r]>A[largest]:
largest=r
if largest!=i:
A[i],A[largest] =A[largest],A[i]
heapify(A,largest,n)


def length(A):return len(A)-1

def buildheap(A):
n=length(A)
for x in xrange(n/2,-1,-1):
print x
heapify(A,x,length(A))

def heapsort(A):
buildheap(A)
heapsize=length(A)
for i in xrange(heapsize,0,-1) :

A[0],A[i]=A[i],A[0]
heapsize=heapsize-1
heapify(A,0,heapsize)

A=[4,8,1,2,11,3,9]
heapsort(A)
print A

Reverse an array without affecting special characters

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

int isalpha(char c)
{
return ((c>='a'&&c<='z')||c>='A'&&c<='Z');
}
int main()
{
string s="a,bc";
int n=s.length()-1;
int i=0;

while(i<n)
{
if(isalpha(s.at(i))&& isalpha( s.at(n)))
{
char t=s.at(i);
s.at(i)=s.at(n);
s.at(n)=t;i++;n--;
}
else if(!isalpha(s.at(i))&&isalpha(s.at(n)))
i++;
else if(!isalpha(s.at(n))&&isalpha(s.at(i)))
n--;
else
i++,n--;
}
cout<<s;
}

Distance between two vertices in Graph

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;

struct graph
{
int e,v;
std::vector< vector <int> > vec;
};

void addEdge(graph *&g,int s,int d)
{
g->vec[s].push_back(d);g->vec[d].push_back(s);
}
graph *create(int v,int e)
{
graph *g=new graph;
g->v=v;
g->e=e;
g->vec.resize(v);

return g;
}
void bfs(graph *g,int k1,int visited[],int dist[])
{
queue <int > s;
s.push(k1);
visited[k1]=1;

for(int i=0;i<100;i++)
dist[i]=-1;
dist[k1]=0;
int k;
while(!s.empty())
{
k=s.front();
s.pop();
cout<<k<<" -> ";

for(int j=0;j<g->vec[k].size();j++)
{
if(dist[g->vec[k][j]]==-1)
{
s.push(g->vec[k][j]);
visited[g->vec[k][j]]=1;
dist[g->vec[k][j]]=dist[k]+1;
}
}
}
}

 int main()

{
int visited[100];

graph*g=create(5,7);
addEdge(g, 0, 1);
    addEdge(g, 0, 4);
    addEdge(g, 1, 2);
    addEdge(g, 1, 3);
    addEdge(g, 1, 4);
    addEdge(g, 2, 3);
    addEdge(g, 3, 4);
   
    cout<<endl;
    int dist[100];
    for(int i=0;i<100;i++)
visited[i]=0,dist[i]=-1;
    bfs(g,2,visited,dist);
    cout<<" Shortest distance between 2 and 0 is "<<dist[0];
return 0;
}

Left View of a Binary Tree

#include <iostream>
using namespace std;
struct node
{
int data;
node *left,*right;
};

void print(node *t)
{

if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}

}
void create(node *&t,int a)
{

if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;
}
else if(a>=t->data)
{
create(t->right,a);
}
else
{
create(t->left,a);
}
}

void leftview(node *t,int level,int &maxlevel)
{
if(!t)
return;
if(maxlevel<level)
{
cout<<t->data<<" ";
maxlevel=level;
}

leftview(t->left,level+1,maxlevel);
leftview(t->right,level+1,maxlevel);
}
int main()
{

int k=0;
node *t;
t=NULL;
int a[]={10,6,4,7,14,12,16,-20,-1};
int i=0;
while(a[i]!=-1)
{
create(t,a[i]);
i++;
}
print(t);
cout<<endl;
int h=0;
leftview(t,1,h);
return 0;
}

Width of Binary Tree

#include <iostream>
#include <fstream>
using namespace std;
int sum[100];
struct node
{
int data;
node *left,*right;
};

void print(node *t)
{

if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}

}

void create(node *&t,int a)
{

if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;
}
else if(a>=t->data)
{
create(t->right,a);
}
else
{
create(t->left,a);
}
}
int max(int a,int b)
{
if(a>b)return a;
return b;
}
int height(node *t)
{
if(t==NULL)return 0;
else
return 1+max(height(t->left),height(t->right));
}
int width(node *t,int l)
{
if(t==NULL)
return 0;
if(l==1)return 1;
if(l>1)
{
return width(t->left,l-1)+width(t->right,l-1);
}
return 0;
}
int treewidth(node *t)
{
int h=height(t);
int maxwidth=0;
for(int i=1;i<=h;i++)
{
int w=width(t,i);
if(w>maxwidth)
maxwidth=w;
}
return maxwidth;
}
int main()
{

int k=0;
node *t;
t=NULL;
int a[]={10,6,4,7,14,12,16,-1};
int i=0;
while(a[i]!=-1)
{
create(t,a[i]);
i++;
}
print(t);
cout<<endl;
cout<<treewidth(t);
return 0;
}

Diameter of a Binary tree

#include <iostream>
using namespace std;
struct node
{
int data;
node * left;
node *right;
};
int height(node *t);
int max(int a ,int b)
{
if(a>b)
return a;
else return b;
}
int diameter(node *t)
{
if(t==NULL)return 0;
int ld=diameter(t->left);
int rd=diameter(t->right);
int lh=height(t->left);
int rh=height(t->right);
return max((lh+rh+1),max(lh,rh));
}
void create(node *&t,int a)
{

if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;

}
else if(a<t->data)
{
create(t->left,a);
}
else {
create(t->right,a);
}


}
void print(node *t)
{
if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}

}

int height(node *t)
{
if(t==NULL)
return 0;
return 1+max(height(t->left),height(t->right));
}

int main()
{int k;
node *t;
t=NULL;
int a[]={10,6,4,7,14,12,16,-1};
int i=0;
while(a[i]!=-1)
{
create(t,a[i]);
i++;
}
print(t);
cout<<diameter(t);
return 0;
}

Sort a linked list that is sorted alternating ascending and descending orders

Input List:   10->40->53->30->67->12->89->NULL
Output List:  10->12->30->43->53->67->89->NULL

#include <iostream>
using namespace std;
struct node {
int data;
node *next;

};

void print(node *t)
{

while(t!=NULL)
{
cout<<t->data<<" ";
t=t->next;
}
cout<<endl;
}
void rev(node *&t)
{
node *temp=NULL;
node *next;
node *cur=t;
while(t!=NULL)
{
next=t->next;
t->next=temp;
temp=t;
t=next;
}
t=temp;
}
void create(node *&t,int a)
{
if(t==NULL)
{
t=new node;
t->data=a;
t->next=NULL;

}
else
{
create(t->next,a);
}
}
node *merge(node *t1,node *t2)
{
node *t=t1;
node *head=t;
t1=t1->next;
while(t1&&t2)
{

t->next=t2;
t=t->next;
t2=t2->next;
if(t1&&t2&&t2->data>t1->data)
{
node *temp=t1;
t1=t2;
t2=temp;
}
}
if(t1!=NULL)
t->next=t1;
else if(t2!=NULL)
t->next=t2;
return  head;
}
int main()
{
int a1[]={10 ,40 ,53 ,30 ,67, 12, 89,'\0'};
int n=7;
node *t=NULL;
for(int i=0;i<n;i++)
{
create(t,a1[i]);
}
print(t);
node *t1=t;
node *h1=NULL;
node *h2=NULL;
while(t1!=NULL&&t1->next!=NULL)
{
create(h1,t1->data);
t1=t1->next;
create(h2,t1->data);
t1=t1->next;
}
if(t1!=NULL)
create(h1,t1->data);
print(h1);

//print(h2);
rev(h2);
print(h2);
t=merge(h1,h2);
print(t);
return 0;
}

Rearrange a given linked list in-place

#include <iostream>
using namespace std;
struct node {
int data;
node *next;

};

void print(node *t)
{

while(t!=NULL)
{
cout<<t->data<<" ";
t=t->next;
}
cout<<endl;
}
void rev(node *&t)
{
node *temp=NULL;
node *next;
node *cur=t;
while(t!=NULL)
{
next=t->next;
t->next=temp;
temp=t;
t=next;
}
t=temp;
}
void create(node *&t,int a)
{
if(t==NULL)
{
t=new node;
t->data=a;
t->next=NULL;

}
else
{
create(t->next,a);
}
}
node *merge(node *t1,node *t2)
{
node *t=t1;
node *head=t;
t1=t1->next;
while(t1&&t2)
{

t->next=t2;
t=t->next;
t2=t2->next;
node *temp=t1;
t1=t2;
t2=temp;

}
if(t1!=NULL)
t->next=t1;
else if(t2!=NULL)
t->next=t2;
return  head;
}
int main()
{
int a1[]={2,23,4,15,6,17,8,'\0'};
int n=7;
node *t=NULL;
for(int i=0;i<n;i++)
{
create(t,a1[i]);
}
print(t);
node *a[100];
node *t1=t;
int i=0;
node *t2=t;

while(t2&&t2->next&&t2->next!=NULL)
{
t1=t1->next;
t2=t2->next->next;
}
if(t2!=NULL)
t1=t1->next;
t2=t;
while(t2->next!=t1)
t2=t2->next;
t2->next=NULL;
print(t);cout<<endl;
print(t1);
rev(t1);
t=merge(t,t1);
print(t);
return 0;
}

Point to next higher value node in a linked list with an arbitrary pointer

#include <iostream>
using namespace std;
struct node {
int data;
node *next;
node *arb;
};


void create(node *&t,int a)
{
if(t==NULL)
{
t=new node;
t->data=a;
t->next=NULL;
t->arb=NULL;
}
else
{
create(t->next,a);
}
}

int main()
{
int a1[]={2,23,4,15,6,17,8,'\0'};
int n=7;
node *t=NULL;
for(int i=0;i<n;i++)
{
create(t,a1[i]);
}
print(t);
node *a[100];
node *t1=t;
int i=0;

while(t1!=NULL)
{
a[i]=t1;
t1=t1->next;
i++;

}

for (int i = 0; i < n-1; i++)
{
/* code */
for(int j=0;j<n-i-1;j++)
{
if(a[j]->data>a[j+1]->data)
{
node *temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}

}
i=0;
while(i<n-1)
{
a[i]->arb=a[i+1];
i++;
}
a[i]->arb=NULL;
while(t->arb!=NULL)
{
cout<<t->data<<" ";
t=t->arb;
}
cout<<t->data;
return 0;
}

print common nodes in BST

#include <iostream>
using namespace std;
struct node
{
int data;
node *left,*right;
};
void print(node *t)
{
if(t!=NULL)
{
cout<<t->data<<" ";
print(t->left);
print(t->right);
}
}
node *newnode(int a)
{
node *t=new node;
t->data=a;
t->left=t->right=NULL;
return t;
}
void create(node *&t,int a)
{
if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;

}
else
{
if(a<t->data)
create(t->left,a);
else
create(t->right,a);
}
}
void printcommon(node *t1,node *t2)
{
if(t1==NULL||t2==NULL)
return ;

if(t1&&t2&&t1->data==t2->data)
cout<<t1->data<<" ";
else if(t1->data>t2->data)
{
printcommon(t1,t2->right);
printcommon(t1->left,t2);
}
else if(t1->data<t2->data){
printcommon(t1->right,t2);
printcommon(t1,t2->left);
}

}
int main()
{
node *t=NULL,*p=NULL;
int a[]={34,12,35,2,46,8,23,95,24};
int b[]={4,12,5,2,46,8,23,9,24};
int n=sizeof(a)/sizeof(a[0]);
cout<<n<<" \n";
int i=0;

for(int i=0;i<n;i++)
{
create(t,a[i]);
create(p,b[i]);
}

printcommon(t,p);

}

Mirror Binary tree

#include <iostream>
using namespace std;
struct node
{
int data;
node *left,*right;
};
void print(node *t)
{
if(t!=NULL)
{
cout<<t->data<<" ";
print(t->left);
print(t->right);
}
}
node *newnode(int a)
{
node *t=new node;
t->data=a;
t->left=t->right=NULL;
return t;
}

bool is_mirror(node *t1,node *t2)
{
if(t1==NULL&t2==NULL)
return true;
else if(t1&&t2&&t1->data==t2->data&&is_mirror(t1->left,t2->right)&&is_mirror(t1->right,t2->left))
return true;
return false;
}
int main()
{
node *t=NULL;
int a[]={34,12,35,2,46,8,23,95,24};
int n=sizeof(a);
int i=0;
t=newnode(3);
t->left=newnode(2);
t->right=newnode(2);
t->left->left=newnode(3);

t->left->right=newnode(4);

t->right->left=newnode(4);

t->right->right=newnode(3);
for(int i=0;i<n;i++)
{
//create(t,a[i]);
}
print(t);
cout<<is_mirror(t,t);
}

Reverse a String Word wise

Given an input string, reverse the string word by word.

Example:

Given s = "the sky is blue",

return "blue is sky the".

#include <iostream>

#include <sstream>

#include <string>

using namespace std;

void reverseWords(string &A) {

       string str="";

       stringstream ss;

      string str1;

      ss<<A;

    while(ss>>str1)

    {

       

       if(str=="")

           str=str1;

        elsea

           str=str1+" "+str;

       

    }

    

    cout<<str;

    A=str;

}

int main()

{

  string str=" hello  hi    ola ----  world ";

  reverseWords(str);

  return 0;

}

Addition and subtraction using Bitwise operators

#include <iostream>
using namespace std;

int add(int a,int b)
{
int sum;
int car;
do
{

sum=a^b;
car=a&b;
a=sum;
b=car<<1;
}
while(b!=0);
return a;
}
int sub(int a,int b)
{

do
{
int car;
car=(~a)&b;
a=a^b;
b=car<<1;
}
while(b!=0);
return a;
}
int main()
{
unsigned int a=5;
int b=2;
cout<<add(a,b)<<"\n";
cout<<sub(a,b);
return 0;
}

write a prgram for to find x^n(x to power of n) using bitwise operators only

int rev(unsigned int byte)

{

unsigned int temp1=0;

unsigned int temp2=0;

unsigned int count=0;

int i;

for(i=0;i<=7;i++)

{

temp1=byte&127;

if(temp1)

{

temp2=temp1|cnt;

}

count=count<<1;

byte=byte<<1;

}

void main()

{

printf("reversse its=%d\n",rev(130));

}

Find Kth smallest element in Binary search tree

/*
TXT file
20 8 22 4 12 10 14 -1
input.txt
*/


#include <iostream>
#include <fstream>
using namespace std;
struct node
{
int data;//,height;
node * left;
node *right;
};
void print(node *t)
{
if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}

}

int height(node *t)
{
if(t==NULL)
return -1;
else{
if(t->left==NULL&&t->right==NULL)
return 0;
else
{
int a=height(t->left);
int b=height(t->right);
if(a>b)
return a+1;
else
return b+1;
}
}
}
int max(int a ,int b)
{
if(a>b)
return a;
else return b;
}

void create(node *&t,int a)
{
if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;
}
else if(a<t->data)
{
create(t->left,a);
}
else {
create(t->right,a);
}
}
void K_small(node *t,int a,int &c)
{
if(t==NULL||c>=a)
return;
K_small(t->left,a,c);
c++;
if(a==c){

cout<<t->data<<" is kth K_small element\n";
return ;
}
K_small(t->right,a,c);
}

int main()
{
ifstream fin;
int k;
fin.open("/home/pawan/Desktop/ds/input.txt");
if(!fin.is_open())

cout<<"file not opened\n";
node *t;
t=NULL;
int a;
fin>>a;
while(a!=-1)
{
create(t,a);
fin>>a;
}

fin.close();
print(t);
cout<<endl;
int c=0;
K_small(t,3,c);
return 0;
}

Find Minimum Height in binary tree

#include <iostream>
#include <fstream>
using namespace std;
struct node
{
int data;//,height;
node * left;
node *right;
};
void print(node *t)
{
if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}

}

int height(node *t)
{
if(t==NULL)
return -1;
else{
if(t->left==NULL&&t->right==NULL)
return 0;
else
{
int a=height(t->left);
int b=height(t->right);
if(a>b)
return a+1;
else
return b+1;
}
}
}
int max(int a ,int b)
{
if(a>b)
return a;
else return b;
}

void create(node *&t,int a)
{
if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;
}
else if(a<t->data)
{
create(t->left,a);
}
else {
create(t->right,a);
}
}
int min_h(node *t)
{
static int h=height(t);
if(t==NULL)
return 0;
if(t->left==NULL&&t->right==NULL)
return 0;
if(t->left==NULL)
return 1+min_h(t->right);
else if(t->right==NULL)
return 1+min_h(t->left);
int a=min_h(t->left);
int b=min_h(t->right);
if(a>b)
return b+1;
else
return a+1;

}
int main()
{
ifstream fin;
int k;
fin.open("/home/pawan/Desktop/ds/input.txt");
if(!fin.is_open())

cout<<"file not opened\n";
node *t;
t=NULL;
int a;
fin>>a;
while(a!=-1)
{
create(t,a);
fin>>a;
}

fin.close();
print(t);
int min=min_h(t);
cout<<"minimun height :";
cout<<min;
return 0;
}

Find longest prefix among strings

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string longestCommonPrefix(vector<string> &A) {
    int in=A[0].length()-1;
   // cout<<in;
    for(int i=0;i<A.size()-1;i++)
    {
        cout<<in<<endl;
        while(A[i][in]!=A[i+1][in]) {
            cout<<"equal";
          in--;
          }
    }
    string str;
    str=A[0].substr(0,in+1);
    return str;
    }
int main()
{
    vector <string> v;
    v.push_back("hello");
    v.push_back("helpp");
    v.push_back("heloo");
    string str=longestCommonPrefix(v);
    cout<<str;
}

Find no. of Trailing zeroes in factorial of given number

trailing zeroes depends on no. of 5's and 2's .

total=no. of 5's.
#include <iostream>
using namespace std;
int main()
{
int a=trailingZeroes(12);
cout<<a;
}
int trailingZeroes(int A) {
    int count=0;
    while(A>=5)
    {
        count=count+A/5;
        A=A/5;
    }
    return count;
}

Merge a linked list into another linked list at alternate positions

#include <iostream>
using namespace std;
struct node
{
int  data;
node *next;
};

void print(node *t)
{
if(t!=NULL)
{

cout<<t->data<<" ";
print(t->next);

}

}

node * create(int  a)
{
node *t=new node;
t->data=a;
t->next=NULL;
return t;
}
node * altswap(node *t,node *l)
{
if(t==NULL )return l;
if(l==NULL) return t;
node *x,*y;
x=t;
while(t&&l){
y=t->next;
t->next=l;
l=y;
t=t->next;
}

return x;
}
int main()
{
node *t=NULL;
t=create(4);
t->next=create(2);
t->next->next=create(11);
t->next->next->next=create(43);
t->next->next->next->next=create(13);
t->next->next->next->next->next=create(45);
node *l=NULL;
l=create(1);
l->next=create(3);
l->next->next=create(12);
l->next->next->next=create(63);
l->next->next->next->next=create(153);
l->next->next->next->next->next=create(145);

print(t);
cout<<endl;
print(l);
cout<<endl;
t=altswap(t,l);
print(t);
return 0;
}