Given two nodes of a Binary Tree, write a program to determine the shortest distance between the two nodes.

Approach:
1. Find the lowest common ancestor of the given nodes.
2. Find the distance (levels) between the lowest common ancestor and each given node separately.
3. Add the distances obtained in Step-2.

#include<iostream>
using namespace std;
struct node
{
 int data;
 struct node* left;
 struct node* right;
};
struct node* createnode(int x)
{
 struct node* new_node=new struct node;
 new_node->data=x;
 new_node->left=NULL;
 new_node->right=NULL;
 return new_node;
};
int help_anc(struct node* root,node* n1,node* n2)
{
    if(root)
    {
        if(root==n1)
        {
            return 1;
        }
        else if(root==n2)
        {
            return 1;
        }
        else
        {
            return help_anc(root->left,n1,n2)+help_anc(root->right,n1,n2);
        }
    }
    else
    {
        return 0;
    }
}
struct node* Ancestor(node* root,node* n1,node* n2)
{
    if(root)
    {
        int lf = help_anc(root->left,n1,n2);
        int rf = help_anc(root->right,n1,n2);
        if(lf==1 && rf==1)
        {
            return root;
        }
        else
        {
            node* lca = Ancestor(root->left,n1,n2);
            if(lca!=NULL)
            {
                return lca;
            }
            lca = Ancestor(root->right,n1,n2);
            return lca;
        }
    }
    else
    {
        return NULL;
    }
}

int customheight(node *root,node *n1,bool *found)
{
    int lheight=0,rheight=0;
    if(root)
    {
        if(*found==false && root==n1)
        {
            *found=true;
            return 0;
        }
        else if(*found==false)
        {
            lheight=customheight(root->left,n1,found);
            rheight=0;
            if(*found==false)
            {
                rheight=customheight(root->right,n1,found);
            }
            if(*found==true)
            {
                return lheight>rheight?1+lheight:1+rheight;
            }
            else
            {
                return 0;
            }
        }
        else
        {
            return 0;
        }
    }
    else
    {
        return 0;
    }
}
int distancethroughlca(node* n1,node* n2,node* lca)
{
    if(lca)
    {
        bool found=false;
        int dist1=customheight(lca,n1,&found);
        cout<<"Distance of "<<n1->data<<": "<<dist1<<endl;
        found=false;
        int dist2=customheight(lca,n2,&found);
        cout<<"Distance of "<<n2->data<<": "<<dist2<<endl;
        return dist1+dist2;
    }
    else
    {
        return 0;
    }
}

int main()
{
    struct node* root=createnode(1);
 root->left=createnode(2);
 root->right=createnode(3);
 root->left->right=createnode(4);
 root->left->left=createnode(5);
 root->right->right=createnode(6);
 root->right->left=createnode(7);
 root->right->right->left=createnode(8);
 //root->right->right->left->left=createnode(10);
 root->right->right->right=createnode(10);
 struct node* n1 = root->right->right->left;
 struct node* n2 = root->right->right->right;
 struct node* lca=Ancestor(root,n1,n2);
 if(lca)
 {
     cout<<"Least Common Ancestor: "<<lca->data<<endl;
 }
 cout<<"Total distance through LCA: "<<distancethroughlca(n1,n2,lca)<<endl;
}
Output:
Least Common Ancestor: 1
Distance of 8: 3
Distance of 4: 2
Total distance through LCA: 5

C++ program for Heapsort

#include<iostream>
#define SIZE 9
using namespace std;
void Maxheapify(int A[SIZE],int i,int heapsize)
{
    int largest=i;
    if(2*i <heapsize && A[i]<A[2*i])
    {
        largest=2*i;
    }
    if(2*i+1 <heapsize && A[largest]<A[2*i+1])
    {
        largest=2*i+1;
    }
    if(largest!=i)
    {
        int t=A[i];
        A[i]=A[largest];
        A[largest]=t;
        Maxheapify(A,largest,heapsize);
    }
}
void Buildmaxheap(int A[SIZE],int heapsize)
{
    int size=heapsize;
    for(int i=size/2;i>=0;i--)
    {
        Maxheapify(A,i,heapsize);
    }
}
void Heapsort(int A[SIZE])
{
    Buildmaxheap(A,SIZE);
    cout<<endl;
    int heapsize=SIZE;
    for(int i=SIZE-1;i>=1;i--)
    {
        int t=A[0];
        A[0]=A[i];
        A[i]=t;
        heapsize--;
        Maxheapify(A,0,heapsize);
    }
}
int main()
{
    int A[SIZE]={9,2,1,8,7,2,4,3,5};
    cout<<"The given array:\n";
    for(int i=0;i<SIZE;i++)
    {
        cout<<A[i]<<" ";
    }
    Heapsort(A);
    cout<<"The sorted array:\n";
    for(int i=0;i<SIZE;i++)
    {
        cout<<A[i]<<" ";
    }
    cout<<endl;
}

Given an array of positive integers, rearrange them so that they together form the largest number

#include<iostream>

#define SIZE 4
using namespace std;

bool decide(int a,int b)
{
    int ta=a,tb=b;
    int pa=1,pb=1;
    while(a>0)
    {
        a/=10;
        pa*=10;
    }
    while(b>0)
    {
        b/=10;
        pb*=10;
    }
    int a_b=ta*pb+tb;//Append b after a.
    int b_a=tb*pa+ta;//Append a after b.
    if(a_b>b_a)
    {
        return false;
    }
    else
    {
        return true;
    }
}

int main()
{
    int A[SIZE]={87,181,9,5};
    //Use any sorting technique but the decide function is the key.
    for(int i=0;i<SIZE;i++)
    {
        for(int j=0;j<SIZE-i-1;j++)
        {
            if(decide(A[j],A[j+1]))
            {
                int t=A[j];
                A[j]=A[j+1];
                A[j+1]=t;
            }
        }
    }
    for(int i=0;i<SIZE;i++)
    {
        cout<<A[i]<<" ";
    }
    cout<<endl;
}
Input:
87 181 9 5
Output:
9 87 5 181

Reverse the adjacent nodes in a linked list

Reverse the adjacent nodes of a linked list as described below in the sample input and output:
Input 1: 1->2->3->4->5
Output1: 2->1->4->3->5
Input2: 1->2->3->4->5->6
Output2: 2->1->4->3->6->5

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

struct node
{
    int data;
    struct node* next;
};

struct node* createlist(int length)
{
    struct node *root=NULL,*end=NULL;
    for(int i=1;i<=length;i++)
    {
        struct node* new_node = (struct node*)malloc(sizeof(struct node));
        new_node->data=i;
        new_node->next=NULL;
        if(i==1)
        {
            root=new_node;
            end=root;
        }
        else
        {
            end->next=new_node;
            end=new_node;
        }
    }
    return root;
}
struct node* reverseadjacent(struct node* root)
{
    int length=0;
    struct node *temp=root;
    while(temp!=NULL)
    {
        length++;
        temp=temp->next;
    }
    if(length<2)
    {
        return root;
    }
    struct node *first=root,*sec=first->next,*third=sec->next;
    root=first->next;
    if(length==2)
    {
        sec->next=first;
        first->next=NULL;
    }
    else if(length%2==0)
    {
        while(third!=NULL)
        {
            first->next=third->next;
            sec->next=first;
            first=third;
            sec=third->next;
            third=sec->next;
        }
        sec->next=first;
        first->next=NULL;
    }
    else
    {
        while(third->next!=NULL)
        {
            first->next=third->next;
            sec->next=first;
            first=third;
            sec=third->next;
            third=sec->next;
        }
        sec->next=first;
        first->next=third;
    }
    return root;
}
void printlist(struct node* root)
{
    struct node* temp=root;
    while(temp!=NULL)
    {
        cout<<temp->data<<"->";
        temp=temp->next;
    }
    cout<<endl;
}
int main()
{
    struct node* root=createlist(5);
    cout<<"The given list\n";
    printlist(root);
    struct node* new_root=reverseadjacent(root);
    cout<<"The new list\n";
    printlist(new_root);
}

Printing all nodes at a given distance from a starting node in a binary tree

#include<iostream>
using namespace std;
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
struct node* createnode(int x)
{
    struct node* new_node=new struct node;
    new_node->data=x;
    new_node->left=NULL;
    new_node->right=NULL;
    return new_node;
};
int printKDistance(node* root,node* start,int k,int *found)
{
    if(root)
    {
        //cout<<root->data<<endl;
        if(k==0)
        {
            cout<<root->data<<endl;
        }
        else if(root==start || *found==1)
        {
            *found=1;
            printKDistance(root->left,start,k-1,found);
            printKDistance(root->right,start,k-1,found);
            return 1;
        }
        else if(*found==0)
        {
            int ldist = printKDistance(root->left,start,k,found);
            //cout<<"ldist="<<ldist<<endl;
            int rdist=0;
            if(*found==0)
            {
                rdist = printKDistance(root->right,start,k,found);
            }
            if((ldist == k || rdist == k) && *found==1)
            {
                cout<<root->data<<endl;
            }
            else
            {
                if(ldist!=0 || rdist!=0)
                return ldist>rdist?1+ldist:1+rdist;
            }
        }
        else
        {
            return 0;
        }
    }
    else
    {
        return 0;
    }
}
int main()
{
    struct node* root=createnode(1);
    root->left=createnode(2);
    root->right=createnode(3);
    root->left->right=createnode(4);
    root->left->left=createnode(5);
    root->right->right=createnode(6);
    root->right->left=createnode(7);
    root->right->right->left=createnode(8);
    //root->right->right->left->left=createnode(10);
    root->right->right->right=createnode(10);
    int k=2;
    //struct node* start = root->right->right->left;
    struct node* start = root->right->left;
    cout<<"start node="<<start->data<<endl;
    cout<<"k="<<k<<endl;
    int a=0;
    int *found=&a;
    printKDistance(root,start,k,found);
}
Output:
start node=7
k=2
Node: 1

Integer Expression Evaluator using Infix-to-Postfix conversion and evaluation of Postfix expression

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

class stack
{
    private:
        int top;
        char A[100];//operator stack array
        int B[100];//operand stack array
    public:
        char pop_oprt();
        void undopop_oprt();
        void push_oprt(char);
        int get_top();
        void displayoprt();
        void init();
        void push_opnd(int);
        int pop_opnd();
};
void stack::init()
{
    top=-1;
}
char stack::pop_oprt()
{
    if(top==-1)
    {
        return 0;
    }
    else
    {
        char t = A[top];
        top--;
        return t;
    }
}
void stack::push_oprt(char val)
{
    top++;
    A[top]=val;
}
void stack::undopop_oprt()
{
    top++;
}
int stack::pop_opnd()
{
    int t = B[top];
    top--;
    return t;
}
void stack::push_opnd(int val)
{
    top++;
    B[top]=val;
}
int stack::get_top()
{
    return top;
}
void stack::displayoprt()
{
    for(int i=top;i>=0;i--)
    {
        cout<<A[i]<<" ";
    }
    cout<<endl;
}
int prcd(char a)
{
    if(a=='(')
    {
        return 0;
    }
    else if(a=='+')
    {
        return 1;
    }
    else if(a=='-')
    {
        return 1;
    }
    else if(a=='/')
    {
        return 2;
    }
    else if(a=='*')
    {
        return 2;
    }
}
int evaluator(char post[100][10],int cnt)
{
    stack opnd;
    opnd.init();
    int i=0;
    while(i<cnt)
    {
        if(isdigit(post[i][0]))
        {
            opnd.push_opnd(atoi(post[i]));
            //opnd.displayoprt();
        }
        else
        {
            int val2 = opnd.pop_opnd();
            int val1 = opnd.pop_opnd();
            if(post[i][0]=='*')
            {
                opnd.push_opnd(val1*val2);
            }
            else if(post[i][0]=='+')
            {
                opnd.push_opnd(val1+val2);
            }
            else if(post[i][0]=='-')
            {
                opnd.push_opnd(val1-val2);
            }
            else if(post[i][0]=='/')
            {
                opnd.push_opnd(val1/val2);
            }
        }
        i++;
    }
    return opnd.pop_opnd();
}
int main()
{
    //char A[100] = "4/2*2+2/2*4";
    char A[100] = "(11+2)*(3+4)";
    stack oprt;
    oprt.init();
    char post[100][10];
    int cnt=00;
    for(int i=0;i<strlen(A);)
    {
        //oprt.displayoprt();
        //getchar();
        int curr_num=0;
        if(isdigit(A[i]))
        {
            while(isdigit(A[i]))
            {
                curr_num = curr_num*10 + A[i]-48;
                i++;
            }
            itoa(curr_num,post[cnt],10);
            cnt++;
        }
        else if(A[i]=='(')
        {
            oprt.push_oprt(A[i]);
            i++;
        }
        else if(A[i]==')')
        {
            while(oprt.pop_oprt()!='(' && oprt.get_top()>-1)
            {
                oprt.undopop_oprt();
                post[cnt][0]=oprt.pop_oprt();
                post[cnt][1]=0;
                cnt++;
            }
            i++;
        }
        else
        {
            //oprt.diplayoprt();
            if(oprt.get_top()==-1)
            {
                oprt.push_oprt(A[i]);
                //cout<<oprt.pop_oprt()<<endl;
            }
            else if(prcd(A[i])>prcd(oprt.pop_oprt()))
            {
                oprt.undopop_oprt();
                oprt.push_oprt(A[i]);
            }
            else
            {
                oprt.undopop_oprt();
                post[cnt][0]=oprt.pop_oprt();
                post[cnt][1]=0;
                cnt++;
                oprt.push_oprt(A[i]);
            }
            i++;
        }
    }
    while(oprt.get_top()>=0)
    {
        post[cnt][0]=oprt.pop_oprt();
        post[cnt][1]=0;
        cnt++;
    }
    cout<<"post-fix"<<endl;
    for(int i=0;i<cnt;i++)
    {
        cout<<post[i]<<endl;
    }
    cout<<"Final value"<<endl;
    cout<<evaluator(post,cnt)<<endl;
}
Output: 91

Finding the Lowest Common Ancestor of two given nodes in a Binary Tree

#include<iostream>
using namespace std;
struct node
{
    int data;
    struct node* left;
    struct node* right;
    struct node* next;
};
struct node* createnode(int x)
{
    struct node* new_node=new struct node;
    new_node->data=x;
    new_node->left=NULL;
    new_node->right=NULL;
    new_node->next=NULL;
    return new_node;
};
int help_anc(struct node* root,node* n1,node* n2)
{
    if(root)
    {
        if(root==n1)
        {
            return 1;
        }
        else if(root==n2)
        {
            return 1;
        }
        else
        {
            return help_anc(root->left,n1,n2)+help_anc(root->right,n1,n2);
        }
    }
    else
    {
        return 0;
    }
}
struct node* Ancestor(node* root,node* n1,node* n2)
{
    if(root)
    {
        int lf = help_anc(root->left,n1,n2);
        int rf = help_anc(root->right,n1,n2);
        if(lf==1 && rf==1)
        {
            return root;
        }
        else
        {
            node* lca = Ancestor(root->left,n1,n2);
            if(lca!=NULL)
            {
                return lca;
            }
            lca = Ancestor(root->right,n1,n2);
            return lca;
        }
    }
    else
    {
        return NULL;
    }
}
int main()
{
    struct node* root=createnode(1);
    root->left=createnode(2);
    root->right=createnode(3);
    root->left->right=createnode(4);
    root->left->left=createnode(5);
    root->right->right=createnode(6);
    root->right->left=createnode(7);
    root->right->right->left=createnode(8);
    //root->right->right->left->left=createnode(10);
    root->right->right->right=createnode(10);
    struct node* n1 = root->right->right->right;
    struct node* n2 = root->left->left;
    struct node* lca=Ancestor(root,n1,n2);
    if(lca)
    {
 cout<<lca->data<<endl;
    }
}
Output:
1

Inorder, Preorder and Postorder Successor and Predecessor Functions inC++

#include<iostream>
using namespace std;
struct node
{
    int data;
    struct node* left;
    struct node* right;
    struct node* next;
};
struct node* createnode(int x)
{
    struct node* new_node=new struct node;
    new_node->data=x;
    new_node->left=NULL;
    new_node->right=NULL;
    new_node->next=NULL;
    return new_node;
}
void inord_succ(struct node* root,struct node** prev)
{
    if(root)
    {
        inord_succ(root->left,prev);
        if(*prev!=NULL)
        {
            (*prev)->next = root;
            *prev = root;
        }
        else
        {
            *prev = root;
        }
        inord_succ(root->right,prev);
    }
}
void inord_pred(struct node* root,struct node** prev)
{
    if(root)
    {
        inord_pred(root->left,prev);
        root->next=*prev;
        *prev=root;
        inord_pred(root->right,prev);
    }
}
void preord_succ(struct node* root,struct node** prev)
{
    if(root)
    {
        if(*prev!=NULL)
        {
            (*prev)->next=root;
            *prev=root;
        }
        else
        {
            *prev=root;
        }
        preord_succ(root->left,prev);
        preord_succ(root->right,prev);
    }
}
void preord_pred(struct node* root,struct node** prev)
{
    if(root)
    {
        root->next=*prev;
        *prev=root;
        preord_pred(root->left,prev);
        preord_pred(root->right,prev);
    }
}
void postord_succ(struct node* root,struct node** prev)
{
    if(root)
    {
        postord_succ(root->left,prev);
        postord_succ(root->right,prev);
        if(*prev!=NULL)
        {
            (*prev)->next=root;
            *prev=root;
        }
        else
        {
            *prev=root;
        }
    }
}
void postord_pred(struct node* root,struct node** prev)
{
    if(root)
    {
        postord_pred(root->left,prev);
        postord_pred(root->right,prev);
        root->next=*prev;
        *prev=root;
    }
}
void inorder(struct node* root)
{
    if(root)
    {
 inorder(root->left);
 cout<<root->data<<" ";
 if(root->next)
 {
     cout<<root->next->data<<endl;
 }
 else
 {
     cout<<endl;
 }
 inorder(root->right);
    }
}
void preorder(struct node* root)
{
    if(root)
    {
        cout<<root->data<<" ";
        if(root->next)
        {
            cout<<root->next->data<<endl;
        }
        else
        {
            cout<<endl;
        }
        preorder(root->left);
        preorder(root->right);
    }
}
void postorder(struct node* root)
{
    if(root)
    {
        postorder(root->left);
        postorder(root->right);
        cout<<root->data<<" ";
        if(root->next)
        {
            cout<<root->next->data<<endl;
        }
        else
        {
            cout<<endl;
        }
    }
}
int main()
{
    struct node* root=createnode(1);
    root->left=createnode(2);
    root->right=createnode(3);
    root->left->right=createnode(4);
    root->left->left=createnode(5);
    root->right->right=createnode(6);
    root->right->left=createnode(7);
    root->right->right->left=createnode(8);
    //root->right->right->left->left=createnode(10);
    root->right->right->right=createnode(10);
    struct node* ptr = NULL;
    //inord_succ(root,&ptr);
    //inord_pred(root,&ptr);
    //inorder(root);
    //preord_succ(root,&ptr);
    //preord_pred(root,&ptr);
    //preorder(root);
    //postord_succ(root,&ptr);
    postord_pred(root,&ptr);
    postorder(root);
    cout<<endl;
}

Number of closed rectangles in a matrix

Given a matrix containing only 1 and 0, find the number of closed rectangles. A closed rectangle is represented by at least one 0 surrounded by eight 1's. There is no overlap of closed rectangles.

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    int rectangle(int A[][10],int i,int j,int d1,int d2,int cnt);
    int A[][10]={
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,1,1,1,1,1,0,0,0},
        {0,0,1,0,0,0,1,0,0,0},
        {0,0,1,0,0,0,1,0,0,0},
        {0,0,1,1,1,1,1,0,0,0},
        {1,1,1,0,0,0,1,1,1,1},
        {0,0,1,0,0,0,1,0,1,1},
        {1,1,1,0,0,0,1,1,1,1}
    };
    int cnt=0;
	for(int i=0;i<8;i++)
    {
        for(int j=0;j<10;j++)
        {
            cout<<A[i][j]<<" ";
        }
        cout<<endl;
    }
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<10;j++)
        {
            if(A[i][j]>0)
            {
                cnt=rectangle(A,i,j,8,10,cnt);
            }
        }
    }
    cout<<"The number of closed rectangles is: "<<cnt<<endl;
}

int rectangle(int A[][10],int i,int j,int d1,int d2,int cnt)
{
    cnt++;
    int rnd=1;
    if(i<d1-1 && j<d2-1 && A[i+1][j+1]==0)
    {
		j++;
		while(j<d2 && i<d1-1 && A[i][j]==1 && A[i+1][j]==0)
		{
			A[i][j]=-1*cnt;
			j++;
		}
		A[i][j]=-1*cnt;
		rnd++;
	}
	if(i<d1-1 && j>0 && A[i+1][j-1]==0 && A[i][j]==-1*cnt)
	{
		i++;
		while(i<d1 && j>0 && A[i][j]==1 && A[i][j-1]==0)
		{
			A[i][j]=-1*cnt;
			i++;
		}
		A[i][j]=-1*cnt;
		rnd++;
	}
	if(i>0 && j>0 && A[i-1][j-1]==0 && A[i][j]==-1*cnt)
	{
		j--;
		while(j>=0 && i>0 && A[i-1][j]==0 && A[i][j]==1)
		{
			A[i][j]=-1*cnt;
			j--;
		}
		A[i][j]=-1*cnt;
		rnd++;
	}
	if(i>0 && j<d2-1 && A[i-1][j+1]==0 && A[i][j]==-1*cnt)
	{
		i--;
		while(i>=0 && j<d2-1 && A[i][j+1]==0 && A[i][j]==1)
		{
			A[i][j]=-1*cnt;
			i--;
		}
		A[i][j]=-1*cnt;
		rnd++;
	}
	if(rnd!=5 || (A[i][j]!=0 && A[i][j]!=A[i][j+1]))
	{
		cnt--;
	}
        return cnt;
}
Output:
The number of closed rectangles is: 2