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

Check if All Leaf Nodes are at same Level in 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);
}
}
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 atsamelevel(node *t,int c,int k)
{
if(!t)return 1;
if(!t->left&&!t->right)
if(c==k)return 1;
else return 0;

return (atsamelevel(t->left,c+1,k)&&atsamelevel(t->right,c+1,k));

}
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;
int h=height(t);
cout<<atsamelevel(t,0,h-1);
return 0;
}

Node at K distance from root 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);
}
}

void atk(node *t,int k,int c)
{
if(t==NULL)
return ;
if(k==c)cout<<t->data<<" ";
atk(t->left,k,c+1);
atk(t->right,k,c+1);

}
int main()
{

int k=2;
node *t;
t=NULL;
int a[]={10,6,4,7,14,12,16,1,2,34,23,-1};
int i=0;
while(a[i]!=-1)
{
create(t,a[i]);
i++;
}
print(t);
cout<<endl;
atk(t,k,0);
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;
}

Given a N*N square matrix, return an array of its anti-diagonals

http://qa.geeksforgeeks.org/4151/return-an-array-of-all-the-anti-diagonals

int n=A.size();
    int N=n-1;
    vector<pair<int,int>> search;
    for(int i=0;i<n;i++)
    {
        search.push_back(make_pair(0,i));
    }
    for(int i=1;i<n;i++)
    {
        search.push_back(make_pair(i,n-1));
    }
    vector <vector <int> > v;
   
    for(int i=0;i<search.size();i++)
    {
        int x=search[i].first;
        int y=search[i].second;
        vector<int > v1;
        while(x<n&&y>=0)
        {
            v1.push_back(A[x][y]);
            x+=1;
            y-=1;
        }
        v.push_back(v1);
    }
    return v;

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

Swap nodes in a linked list without swapping data

#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 * swap(node *t,int a,int b)
{
if(t==NULL ||t->next==NULL)
return t;
node *x,*y;
x=t;
while(x->data!=a&&x)
x=x->next;
y=t;
while(y->data!=b)
y=y->next;

node *m=y->next;
node *t1=t;
while(t1->next!=x&&t1->next)
t1=t1->next;
t1->next=y;
y->next=x->next;
node *y1=y;
while(y->next!=y1)
y=y->next;
y->next=x;
x->next=m;
return t;
}
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);
print(t);
cout<<endl;
t=swap(t,2,13);
print(t);
return 0;
}