Write a function to get the number of vertices in an undirected graph and its edges. You may assume that no edge is input twice.(ADJACENCY MATRIX)

#include<iostream>
#include<queue>
#include<stack>
// Name : Vivek S. Sharma
using namespace std;
class Graph{
int g[10][10];
int v[10];
int n,e;
public:
void create(){
int v1,v2;
cout<<"\nEnter no. of vertices : ";
cin>>n;
cout<<"\nEnter no. of edges : ";
cin>>e;
for(int i=1; i<=n ; i++){
for(int j=1; j<=n ; j++){
g[i][j]=0;
v[i]=0;
}
}
for(int i=1; i<=e ;i++ ){
cout<<"\nEnter the edge : ";
cin>>v1>>v2;
g[v1][v2]=g[v2][v1]=1;
}
}
void bfs(){
int v1,v2;
cout<<"\nEnter the starting vertex : ";
cin>>v1;
queue<int> q;
q.push(v1);
v[v1]=1;
while(!q.empty()){
v1=q.front();
q.pop();
cout<<v1;
for( v2=1; v2<=n ; v2++){
if(g[v1][v2]==1 && v[v2]==0){
q.push(v2);
v[v2]=1;}
}

}
}

void dfs(){
int v1,v2;
cout<<"\nEnter starting vertex : ";
cin>>v1;
stack <int> s;
s.push(v1);
while(!s.empty()){
v1=s.top();
s.pop();
if(v[v1]==0){
cout<<v1;
v[v1]=1;
}
for(v2=1; v2<=n ; v2++){
if(g[v1][v2]==1 && v[v2]==0)
s.push(v2);
}
}
}
void dfs_recurssion(int v1){

int v2;
cout<<v1;
v[v1]=1;
for( v2=1; v2<=n ; v2++){
if(g[v1][v2]==1 && v[v2]==0)
dfs_recurssion(v2);
}
}
};

int main(){
Graph g;
int v;
g.create();
/*cout<<"\nEnter the starting vertex : ";
cin>>v;
g.dfs_recurssion(v);
//g.dfs();*/
g.bfs();
return 0;
}

Implement the Heap/Shell sort algorithm implemented in Java demonstrating heap/shell data structure with modularity of programming language.

//////////////////////////////////////////////////////////////
// //
//   Name : Vivek S. Sharma //
// Title : Heap Sort //
// //
// //
//////////////////////////////////////////////////////////////
package vivek_a12;
import java.util.*;
public class vivek_a12 {

private static int N;
    public static void sort(int arr[]){     
heapMethod(arr);       
        for (int i = N; i > 0; i--){
            swap(arr,0, i);
            N = N-1;
            heap(arr, 0);
        }
    }   
    public static void heapMethod(int arr[]){
        N = arr.length-1;
        for (int i = N/2; i >= 0; i--)
            heap(arr, i);       
    }
    public static void heap(int arr[], int i){
        int left = 2*i ;
        int right = 2*i + 1;
        int max = i;
        if (left <= N && arr[left] > arr[i])
            max = left;
if (right <= N && arr[right] > arr[max])       
            max = right;
        if (max != i){
            swap(arr, i, max);
            heap(arr, max);
        }
    }   
    public static void swap(int arr[], int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }   
    public static void main(String[] args) {
        Scanner in = new Scanner( System.in );     
        int n;   
        System.out.println("Enter the number of elements to be sorted:");
        n = in.nextInt();   
        int arr[] = new int[ n ];
        System.out.println("Enter "+ n +" integer elements");
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        sort(arr);
        System.out.println("After sorting ");       
        for (int i = 0; i < n; i++)
            System.out.println(arr[i]+" ");           
        System.out.println();           
    }   

}

Department maintains a student information. The file contains roll number, name, division and address. Allow user to add, delete information of student. Display information of particular employee. If record of student does not exist an appropriate message is displayed. If it is, then the system displays the student details. Use sequential file to main the data.

#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
class tel
 {

 public:
int rollNo,roll1;
char name[10];
char div;
char address[20];
void accept()
{
cout<<"\n\tEnter Roll Number : ";
cin>>rollNo;
cout<<"\n\tEnter the Name : ";
cin>>name;
cout<<"\n\tEnter the Division:";
cin>>div;
cout<<"\n\tEnter the Address:";
cin>>address;
}
        void accept2()
        {
               cout<<"\n\tEnter the Roll No. to modify : ";
               cin>>rollNo;
        }
        void accept3()
        {
              cout<<"\n\tEnter the name to modify : ";
              cin>>name;
        }
        int getRollNo()
        {
        return rollNo;
        }
void show()
{

cout<<"\n\t"<<rollNo<<"\t\t"<<name<<"\t\t"<<div<<"\t\t"<<address;
}
};
int main()
{
int i,n,ch,ch1,rec,start,count,add,n1,add2,start2,n2,y,a,b,on,oname,add3,start3,n3,y1,add4,start4,n4;
char name[20],name2[20];
tel t1;
count=0;
fstream g,f;
do
{
cout<<"\n>>>>>>>>>>>>>>>>>>>>>>MENU<<<<<<<<<<<<<<<<<<<<";
cout<<"\n1.Insert and overwrite\n2.Show\n3.Search & Edit(number)\n4.Search & Edit(name)\n5.Search & Edit(onlynumber)\n6.Search & edit(only name)\n 7.Delete a Student Record\n 8.Exit\n\tEnter the Choice\t:";
cin>>ch;
switch(ch)
{
case 1:
f.open("StuRecord.txt",ios::out);
x:t1.accept();
f.write((char*) &t1,(sizeof(t1)));
cout<<"\nDo you want to enter more records?\n1.Yes\n2.No";
cin>>ch1;
if(ch1==1)
goto x;
else
{
f.close();
break;
}

case 2:
f.open("StuRecord.txt",ios::in);
f.read((char*) &t1,(sizeof(t1)));
//cout<<"\n\tRoll No.\t\tName \t\t Division \t\t Address";
while(f)
{
t1.show();
f.read((char*) &t1,(sizeof(t1)));
}
f.close();
break;
case 3:
cout<<"\nEnter the roll number you want to find";
cin>>rec;
f.open("StuRecord.txt",ios::in|ios::out);
f.read((char*)&t1,(sizeof(t1)));
while(f)
{
if(rec==t1.rollNo)
{
cout<<"\nRecord found";
add=f.tellg();
f.seekg(0,ios::beg);
       start=f.tellg();
n1=(add-start)/(sizeof(t1));
f.seekp((n1-1)*sizeof(t1),ios::beg);
t1.accept();
f.write((char*) &t1,(sizeof(t1)));
f.close();
count++;
break;
}
f.read((char*)&t1,(sizeof(t1)));
     }
if(count==0)
        cout<<"\nRecord not found";
f.close();
break;

case 4:
cout<<"\nEnter the name you want to find and edit";
cin>>name;
f.open("StuRecord.txt",ios::in|ios::out);
f.read((char*)&t1,(sizeof(t1)));
while(f)
{
y=(strcmp(name,t1.name));
if(y==0)
{
cout<<"\nName found";
add2=f.tellg();
f.seekg(0,ios::beg);
start2=f.tellg();
n2=(add2-start2)/(sizeof(t1));
f.seekp((n2-1)*sizeof(t1),ios::beg);
t1.accept();
f.write((char*) &t1,(sizeof(t1)));
f.close();
break;
}
        f.read((char*)&t1,(sizeof(t1)));
}
break;
     case 5:
           cout<<"\n\tEnter the roll number you want to modify";
           cin>>on;
           f.open("StuRecord.txt",ios::in|ios::out);
           f.read((char*) &t1,(sizeof(t1)));
           while(f)
           {
             if(on==t1.rollNo)
             {
               cout<<"\n\tNumber found";
               add3=f.tellg();
               f.seekg(0,ios::beg);
               start3=f.tellg();
               n3=(add3-start3)/(sizeof(t1));
               f.seekp((n3-1)*(sizeof(t1)),ios::beg);
               t1.accept2();
               f.write((char*)&t1,(sizeof(t1)));
               f.close();
               break;
             }
             f.read((char*)&t1,(sizeof(t1)));
          }
          break;
     case 6:
           cout<<"\nEnter the name you want to find and edit";
cin>>name2;
f.open("StuRecord.txt",ios::in|ios::out);
f.read((char*)&t1,(sizeof(t1)));
while(f)
{
y1=(strcmp(name2,t1.name));
if(y1==0)
{
cout<<"\nName found";
add4=f.tellg();
f.seekg(0,ios::beg);
start4=f.tellg();
n4=(add4-start4)/(sizeof(t1));
f.seekp((n4-1)*sizeof(t1),ios::beg);
t1.accept3();
f.write((char*) &t1,(sizeof(t1)));
f.close();
break;
}
        f.read((char*)&t1,(sizeof(t1)));
}
break;
   case 7:
    int roll;
    cout<<"Please Enter the Roll No. of Student Whose Info You Want to Delete: ";
  cin>>roll;
  f.open("StuRecord.txt",ios::in);
  g.open("temp.txt",ios::out);
  f.read((char *)&t1,sizeof(t1));
  while(!f.eof())
  {
    if (t1.getRollNo() != roll)
      g.write((char *)&t1,sizeof(t1));
      f.read((char *)&t1,sizeof(t1));
  }
  cout << "The record with the roll no. " << roll << " has been deleted " << endl;
  f.close();
  g.close();
  remove("StuRecord.txt");
  rename("temp.txt","StuRecord.txt");
    break;
   case 8:
      cout<<"\n\tThank you";
      break;


        }
  }while(ch!=8);
}

Read the marks obtained by students of second year in an online examination of particular subject. Find out maximum and minimum marks obtained in that subject. Use heap data structure. Analyze the algorithm.

#include <iostream>
//////////////////////////////////////////////////////////////
// //
//   Name : Vivek S. Sharma //
// Title : Heap Sort //
// //
// //
//////////////////////////////////////////////////////////////
using namespace std;


void MaxHeapify(int a[], int i, int n)
{
int j, temp;
temp = a[i];
j = 2*i;

  while (j <= n)
{
if (j < n && a[j+1] > a[j])
j = j+1;

if (temp > a[j])
break;

else if (temp <= a[j])
{
a[j/2] = a[j];
j = 2*j;
}
}
a[j/2] = temp;
return;
}
void MinHeapify(int a[], int i, int n)
{
int j, temp;
temp = a[i];
j = 2*i;

  while (j <= n)
{
if (j < n && a[j+1] < a[j])
j = j+1;

if (temp < a[j])
break;

else if (temp >= a[j])
{
a[j/2] = a[j];
j = 2*j;
}
}
a[j/2] = temp;
return;
}
void MaxHeapSort(int a[], int n)
{
int i, temp;
for (i = n; i >= 2; i--)
{

temp = a[i];
a[i] = a[1];
a[1] = temp;

MaxHeapify(a, 1, i - 1);
}
}
void MinHeapSort(int a[], int n)
{
int i, temp;
for (i = n; i >= 2; i--)
{

temp = a[i];
a[i] = a[1];
a[1] = temp;

MinHeapify(a, 1, i - 1);
}
}
void Build_MaxHeap(int a[], int n)
{
int i;
for(i = n/2; i >= 1; i--)
MaxHeapify(a, i, n);
}
void Build_MinHeap(int a[], int n)
{
int i;
for(i = n/2; i >= 1; i--)
MinHeapify(a, i, n);
}
int main()
{
int n, i;
cout<<"\nEnter the number of Students : ";
cin>>n;
n++;
int arr[n];
for(i = 1; i < n; i++)
{
cout<<"Enter the marks :  "<<i<<": ";
cin>>arr[i];
}

Build_MaxHeap(arr, n-1);
MaxHeapSort(arr, n-1);


int max,min;
cout<<"\nSorted Data : ASCENDING : ";

for (i = 1; i < n; i++)
cout<<"->"<<arr[i];
min=arr[1];
Build_MinHeap(arr, n-1);
MinHeapSort(arr, n-1);
cout<<"\nSorted Data : DESCENDING: ";
max=arr[1];
for (i = 1; i < n; i++)
cout<<"->"<<arr[i];
cout<<"\nMaximum Marks : "<<max<<"\nMinimum marks : "<<min;
return 0;
}

Consider telephone book database of N clients. Make use of a hash table implementation to quickly look up client‘s telephone number.

#include<iostream>
//////////////////////////////////////////////////////////////
// //
//   Name : Vivek S. Sharma //
// Title : Hashing with sll //
// //
// //
//////////////////////////////////////////////////////////////
using namespace std;
 struct node{
int value;
node* next;
}*HashTable[10];
class hashing{
public:

hashing(){

for(int i=0 ; i<10 ; i++){
HashTable[i]=NULL;
}
}


int HashFunction(int value){
return (value%10);
}

node* create_node(int x){
node* temp=new node;
temp->next=NULL;
temp->value=x;
return temp;
}

void display(){
for(int i=0 ; i< 10; i++){
node * temp=new node;
temp=HashTable[i];
cout<<"a["<<i<<"] : ";
while(temp !=NULL){
cout<<" ->"<<temp->value;
temp=temp->next;
}
cout<<"\n";
}
}


int searchElement(int value){
bool flag = false;
            int hash_val = HashFunction(value);
            node* entry = HashTable[hash_val];
            cout<<"\nElement found at : ";
            while (entry != NULL)
    {
                if (entry->value==value)
        {
                    cout<<hash_val<<" : "<<entry->value<<endl;
                    flag = true;
                }
                entry = entry->next;
            }
            if (!flag)
                return -1;
}

void deleteElement(int value){
int hash_val = HashFunction(value);
            node* entry = HashTable[hash_val];

            if (entry == NULL )
            {
            cout<<"No Element found ";
                return;
            }

            if(entry->value==value){
            HashTable[hash_val]=entry->next;
            return;
            }
            while ((entry->next)->value != value)
    {
                entry = entry->next;
            }
            entry->next=(entry->next)->next;


}

void insertElement(int value){
int hash_val = HashFunction(value);
           // node* prev = NULL;
            //node* entry = HashTable[hash_val];
            node* temp=new node;
            node* head=new node;
            head = create_node(value);
            temp=HashTable[hash_val];
            if (temp == NULL)
                        {

                           HashTable[hash_val] =head;
                            }
            else{
            while (temp->next != NULL)

            {
                temp = temp->next;
            }

                    temp->next =head;

            }


}
};

int main(){
int ch;
int data,search,del;
hashing h;
do{
cout<<"\nTelephone : \n1.Insert \n2.Display \n3.Search \n4.Delete \n5.Exit";
cin>>ch;
switch(ch){
case 1:cout<<"\nEnter phone no. to be inserted : ";
cin>>data;
h.insertElement(data);
break;
case 2:h.display();
break;
case 3:cout<<"\nEnter the no to be searched : ";
cin>>search;

if (h.searchElement(search) == -1)
            {
        cout<<"No element found at key ";
        continue;
            }
break;
case 4:cout<<"\nEnter the phno. to be deleted : ";
cin>>del;
h.deleteElement(del);
cout<<"Phno. Deleted"<<endl;
break;
}
}while(ch!=5);
return 0;
}

Implement all the functions of a dictionary (ADT) using hashing. Data: Set of (key, value) pairs, Keys are mapped to values, Keys must be comparable, Keys must be unique Standard Operations: Insert(key, value), Find(key), Delete(key)

#include<iostream>
#include<string.h>
//////////////////////////////////////////////////////////////
// //
//   Name : Vivek S. Sharma //
// Title : Hashing with probing //
// //
// //
//////////////////////////////////////////////////////////////
using namespace std;

class HashFunction
  {
     typedef struct hash
{
long key;
char name[10];
}hash;
hash h[10];
   public:
HashFunction();
void insert();
void display();
int find(long);
void Delete(long);


  };

HashFunction::HashFunction()
  {
int i;
for(i=0;i<10;i++)
  {
h[i].key=-1;
strcpy(h[i].name,"NULL");
  }
  }
void HashFunction::Delete(long k)
  {
int index=find(k);
if(index==-1)
  {
cout<<"\n\tKey Not Found";
  }
else
  {
h[index].key=-1;
strcpy(h[index].name,"NULL");
cout<<"\n\tKey is Deleted";
  }


  }
int HashFunction::find(long k)
  {
int i;
for(i=0;i<10;i++)
  {
if(h[i].key==k)
  {
cout<<"\n\t"<<h[i].key<<" is Found at "<<i<<" Location With Name "<<h[i].name;
return i;
  }
  }
if(i==10)
      {
return -1;
  }

  }


void HashFunction::display()
  {
int i;
cout<<"\n\t\tKey\t\tName";
for(i=0;i<10;i++)
    {
cout<<"\n\th["<<i<<"]\t"<<h[i].key<<"\t\t"<<h[i].name;
  }
  }

void HashFunction::insert()
  {
char ans,n[10],ntemp[10];
long k,temp;
int v,hi,cnt=0,flag=0,i;

do
  {
if(cnt>=10)
  {
cout<<"\n\tHash Table is FULL";
break;
  }
cout<<"\n\tEnter a Telephone No: ";
cin>>k;
cout<<"\n\tEnter a Client Name: ";
cin>>n;
hi=k%10;// hash function
if(h[hi].key==-1)
  {
h[hi].key=k;
strcpy(h[hi].name,n);
  }
     else
    {

if(h[hi].key%10!=hi)
  {
temp=h[hi].key;
strcpy(ntemp,h[hi].name);
h[hi].key=k;
strcpy(h[hi].name,n);
for(i=hi+1;i<10;i++)
    {
if(h[i].key==-1)
    {
h[i].key=temp;
strcpy(h[i].name,ntemp);
flag=1;
break;
      }
    }
for(i=0;i<hi && flag==0;i++)
    {
if(h[i].key==-1)
    {
h[i].key=temp;
strcpy(h[i].name,ntemp);
break;
      }
         }
    }
else
  {
for(i=hi+1;i<10;i++)
    {
if(h[i].key==-1)
    {
h[i].key=k;
strcpy(h[i].name,n);
flag=1;
break;
      }
    }
for(i=0;i<hi && flag==0;i++)
    {
if(h[i].key==-1)
    {
h[i].key=k;
strcpy(h[i].name,n);
break;
      }
       }
  }

  }
    flag=0;
     cnt++;
     cout<<"\n\t..... Do You Want to Insert More Key: y/n";
     cin>>ans;
  }while(ans=='y'||ans=='Y');

  }



int main()
  {
long k;
int ch,index;
char ans;
HashFunction obj;
do
  {
cout<<"\n\t***** Telephone (ADT) *****";
cout<<"\n\t1. Insert\n\t2. Display\n\t3. Find\n\t4. Delete\n\t5. Exit";
cout<<"\n\t..... Enter Your Choice: ";
cin>>ch;
switch(ch)
  {
case 1: obj.insert();
break;
case 2: obj.display();
break;
case 3: cout<<"\n\tEnter a Key Which You Want to Search: ";
cin>>k;
index=obj.find(k);
if(index==-1)
  {
cout<<"\n\tKey Not Found";
  }
break;
case 4: cout<<"\n\tEnter a Key Which You Want to Delete: ";
cin>>k;
obj.Delete(k);
break;
case 5:
break;
  }
cout<<"\n\t..... Do You Want to Continue in Main Menu:y/n ";
cin>>ans;
  }while(ans=='y'||ans=='Y');
  }

A Dictionary stores keywords & its meanings. Provide facility for adding new keywords, deleting keywords, updating values of any entry. Provide facility to display whole data sorted in ascending/ Descending order. Also find how many maximum comparisons may require for finding any keyword. Use Binary Search Tree for implementation.

#include"iostream"
#include<string.h>
using namespace std;
//////////////////////////////////////////////////////////////
// //
//   Name : Vivek S. Sharma //
// Title : BST //
// //
// //
//////////////////////////////////////////////////////////////
typedef struct node
{

 char k[20];
 char m[20];
 class node  *left;
 class node * right;
}node;

class dict
{
public:
 node *root;
 void create();
 void disp(node *);
 void insert(node * root,node *temp);
 int search(node *,char []);
 int update(node *,char []);
 node* del(node *,char []);
 node * min(node *);
};

void dict :: create()
{
 class node *temp;
 int ch;

 do
 {
  temp = new node;
  cout<<"\nEnter Keyword:";
  cin>>temp->k;
  cout<<"\nEnter Meaning:";
  cin>>temp->m;

  temp->left = NULL;
  temp->right = NULL;

  if(root == NULL)
  {
   root = temp;
  }
  else
  {
   insert(root, temp);
  }
  cout<<"\nDo u want to add more (y=1/n=0):";
  cin>>ch;
 }
 while(ch == 1);

}

void dict ::  insert(node * root,node *temp)
{
 if(strcmp (temp->k, root->k) < 0 )
 {
  if(root->left == NULL)
   root->left = temp;
  else
   insert(root->left,temp);
 }
 else
 { if(root->right == NULL)
   root->right = temp;
  else
   insert(root->right,temp);
 }

}

void dict:: disp(node * root)
{
 if( root != NULL)
 {
  disp(root->left);
  cout<<"\n Key Word :"<<root->k;
  cout<<"\t Meaning :"<<root->m;
  disp(root->right);
 }
}

int dict :: search(node * root,char k[20])
{
 int c=0;
 while(root != NULL)
 {
  c++;
  if(strcmp (k,root->k) == 0)
  {
   cout<<"\nNo of Comparisons:"<<c;
   return 1;
  }
  if(strcmp (k, root->k) < 0)
   root = root->left;
  if(strcmp (k, root->k) > 0)
   root = root->right;
 }

 return -1;
}
int dict :: update(node * root,char k[20])
{
 while(root != NULL)
 {
  if(strcmp (k,root->k) == 0)
  {
   cout<<"\nEnter New Meaning ofKeyword"<<root->k;
   cin>>root->m;
   return 1;
  }
  if(strcmp (k, root->k) < 0)
   root = root->left;
  if(strcmp (k, root->k) > 0)
   root = root->right;
 }
 return -1;
}
node* dict :: del(node * root,char k[20])
{
 node *temp;

 if(root == NULL)
 {
  cout<<"\nElement No Found";
  return root;
 }

 if (strcmp(k,root->k) < 0)
 {
  root->left = del(root->left, k);
  return root;
 }
 if (strcmp(k,root->k) > 0)
 {
   root->right = del(root->right, k);
   return root;
 }

 if (root->right==NULL&&root->left==NULL)
 {
  temp = root;
  delete temp;
  return NULL;
  }
  if(root->right==NULL)
  {
  temp = root;
  root = root->left;
  delete temp;
  return root;
  }
  else if(root->left==NULL)
  {
  temp = root;
  root = root->right;
  delete temp;
  return root;
  }
  temp = min(root->right);
  strcpy(root->k,temp->k);
  root->right = del(root->right, temp->k);
  return root;

}

node * dict :: min(node *q)
{
 while(q->left != NULL)
 {
  q = q->left;
 }
 return q;
}



int main()
{
 int ch;
 dict d;
 d.root = NULL;


 do
 {
  cout<<"\nMenu\n1.Create\n2.Disp\n3.Search\n4.Update\n5.Delete\nEnter Ur CH:";
  cin>>ch;

  switch(ch)
  {
case 1: d.create();
  break;
case 2: if(d.root == NULL)
  {
  cout<<"\nNo any Keyword";
  }
  else
  {
  d.disp(d.root);
  }
  break;
case 3: if(d.root == NULL)
 {
  cout<<"\nDictionary is Empty. First add keywords then try again ";
 }
  else
 {

        cout<<"\nEnter Keyword which u want to search:";
  char k[20];
  cin>>k;

  if( d.search(d.root,k) == 1)
  cout<<"\nKeyword Found";
  else
  cout<<"\nKeyword Not Found";
 }
  break;
case 4:
  if(d.root == NULL)
  {
  cout<<"\nDictionary is Empty. First add keywords then try again ";
 }
  else
  {
  cout<<"\nEnter Keyword which meaning  want to update:";
  char k[20];
  cin>>k;
  if(d.update(d.root,k) == 1)
  cout<<"\nMeaning Updated";
  else
  cout<<"\nMeaning Not Found";
  }
  break;
case 5:
  if(d.root == NULL)
  {
  cout<<"\nDictionary is Empty. First add keywords then try again ";
  }
  else
  {
  cout<<"\nEnter Keyword which u want to delete:";
  char k[20];
  cin>>k;
  if(d.root == NULL)
  {
  cout<<"\nNo any Keyword";
  }
  else
  {
  d.root = d.del(d.root,k);
    }
   }
  }
 }
 while(ch<=5);
 return 0;

}

For given expression eg. a-b*c-d/e+f construct inorder sequence and traverse it using postorder traversal(non recursive).

#include<iostream>
#include<stack>
using namespace std;
//////////////////////////////////////////////////////////////
// //
//   Name : Vivek S. Sharma //
// Title : BST Expression Conversion //
// //
// //
//////////////////////////////////////////////////////////////
class Btree{
typedef struct node{
int data;
struct node * right ,*left;
}node;

public :
node * root,*temp;
Btree(){
root=new node;
root=NULL;
}
void create(){
temp=new node;

cout<<"\nEnter the data : ";
cin>>temp->data;
temp->left=temp->right=NULL;
if(root==NULL){
root=temp;
}
else{
insert(root,temp);
}
}

void insert(node * root, node * temp){
char ch;
cout<<"\nDo u want to enter "<<temp->data<<" as left or rright child of "<<root->data<<" : ";
cin>>ch;
if(ch=='l'){
if(root->left==NULL){
root->left=temp;
}
else
insert(root->left,temp);
}
else{
if(root->right==NULL)
root->right=temp;
else
insert(root->right,temp);
}

}
void postOrder_recursive(node * root){
if(root!=NULL){
postOrder_recursive(root->left);
postOrder_recursive(root->right);
cout<<"\t "<<root->data;
}
}
void postOrder_nonRecursive(node* root){
if(!root)
{
cout<<"\nEmpty";
return;
}
stack<node *> s;
stack<node*> p;
s.push(root);
while(!s.empty()){
node * cur=s.top();
p.push(cur);
s.pop();
if(cur->left)
s.push(cur->left);
if(cur->right)
s.push(cur->right);
}
while(!p.empty()){
cout<<"\t"<<p.top()->data;
p.pop(); }
}
//Extra Part : Inorder
void InOrder_nonRecursive(node* root){
if(!root)
{
cout<<"\nEmpty";
return;
}
stack<node *> s;
stack<node*> p;

while(true){
while(root!=NULL){
//cout<<"\t "<<root->data;
s.push(root);
root=root->left;
}
if(s.empty())
return;
root=s.top();
s.pop();

cout<<"\t "<<root->data;
root=root->right;
}
}
//Extra Part : PreOrder
void PreOrder_nonRecursive(node* root){
if(!root)
{
cout<<"\nEmpty";
return;
}
stack<node *> s;
stack<node*> p;

while(true){
while(root!=NULL){
cout<<"\t "<<root->data;
s.push(root);
root=root->left;
}
if(s.empty())
return;
root=s.top();
s.pop();

//cout<<"\t "<<root->data;
root=root->right;
}
}
void display(node* root, int space){

if(root==NULL)
return ;
space +=3;
display(root->right,space);
cout<<"\n";
for(int i=3; i<=space ; i++){
cout<<"  ";}
cout<<root->data<<"\n";
display(root->left,space);
}

};
int main(){
Btree b;
int ch;
do{
b.create();
cout<<"\nDo u wnat to insert more elements :1/0 ";
cin>>ch;

}while(ch!=0);
b.display(b.root,0);
cout<<"\nRecursive Post Order : ";
b.postOrder_recursive(b.root);
cout<<"\nNon Recursive Post Order : ";
b.postOrder_nonRecursive(b.root);
cout<<"\nNon Recursive In Order : ";
b.InOrder_nonRecursive(b.root);
cout<<"\nNon Recursive Pre Order : ";
b.PreOrder_nonRecursive(b.root);
return 0;
}