2020UCA1903

#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
using namespace std;

struct node
{
	string train_name;
	string train_no;
	string ticket_no;
	string cost;
	string passenger_id;
	struct node *left;
	struct node *right;
};

struct node *root;

struct node *create(string train_name, string train_no, string ticket_no, string cost, string passenger_id)
{
	struct node *ptr = (struct node *)malloc(sizeof(struct node));
	ptr->train_name = train_name;
	ptr->train_no = train_no;
	ptr->ticket_no = ticket_no;
	ptr->cost = cost;
	ptr->passenger_id = passenger_id;
	return ptr;
}

struct node *insert(struct node *ptr, string train_name, string train_no, string ticket_no, string cost, string passenger_id, map<string, int> &ct)
{
	if (ptr == NULL)
	{
		ptr = create(train_name, train_no, ticket_no, cost, passenger_id);
		ct[train_name]++;
	}
	else
	{
		if (ptr->passenger_id < passenger_id)
		{
			ptr->right = insert(ptr->right, train_name, train_no, ticket_no, cost, passenger_id, ct);
		}
		else
		{
			ptr->left = insert(ptr->left, train_name, train_no, ticket_no, cost, passenger_id, ct);
		}
	}

	return ptr;
}

struct node *inorder_successor(struct node *ptr)
{
	struct node *current = (struct node *)malloc(sizeof(struct node));

	while (current && current->left != NULL)
		current = current->left;

	return current;
}

struct node *remove(struct node *ptr, string passenger_id, map<string, int> &ct)
{
	if (ptr == NULL)
	{
		return ptr;
	}

	if (ptr->passenger_id < passenger_id)
	{
		ptr->right = remove(ptr->right, passenger_id, ct);
	}
	else if (ptr->passenger_id > passenger_id)
	{
		ptr->left = remove(ptr->left, passenger_id, ct);
	}

	else
	{
		if (ptr->left == NULL && ptr->right == NULL)
		{
			ct[ptr->train_name]--;
			free(ptr);
			return NULL;
		}
		else if (ptr->left == NULL)
		{
			ct[ptr->train_name]--;
			struct node *temp = ptr->right;
			free(ptr);
			return temp;
		}
		else if (ptr->right == NULL)
		{
			ct[ptr->train_name]--;
			struct node *temp = ptr->left;
			free(ptr);
			return temp;
		}

		ct[ptr->train_name]--;
		struct node *temp = inorder_successor(ptr->right);
		ptr->train_name = temp->train_name;
		ptr->train_no = temp->train_no;
		ptr->ticket_no = temp->ticket_no;
		ptr->cost = temp->cost;
		ptr->passenger_id = temp->passenger_id;
		ptr->right = remove(ptr->right, passenger_id, ct);
	}

	return ptr;
}
int Height(struct node *ptr)
{
	if (ptr == NULL)
	{
		return -1;
	}

	return max(Height(ptr->left), Height(ptr->right)) + 1;
}
void display_leaf_node(struct node *ptr)
{
	if (ptr == NULL)
	{
		return;
	}
	else if (ptr->left == NULL && ptr->right == NULL)
	{
		cout << left<<setw(15)<<setfill(' ')<<ptr->train_name  <<left<<setw(15)<<setfill(' ') << ptr->train_no << left<<setw(15)<<setfill(' ')<< ptr->ticket_no <<  left<<setw(15)<<setfill(' ')<< ptr->cost <<  left<<setw(15)<<setfill(' ')<< ptr->passenger_id << endl;
		return;
	}

	display_leaf_node(ptr->left);
	display_leaf_node(ptr->right);
}
void inorder_traversal(struct node *ptr)
{
	if (ptr == NULL)
	{
		return;
	}

	cout << left<<setw(15)<<setfill(' ')<<ptr->train_name  <<left<<setw(15)<<setfill(' ') << ptr->train_no << left<<setw(15)<<setfill(' ')<< ptr->ticket_no <<  left<<setw(15)<<setfill(' ')<< ptr->cost <<  left<<setw(15)<<setfill(' ')<< ptr->passenger_id << endl;
	inorder_traversal(ptr->left);
	inorder_traversal(ptr->right);
}

bool sortbysec(const pair<int, int> &a,
			   const pair<int, int> &b)
{
	return (a.second < b.second);
}

int main()
{
	root = NULL;
	map<string, int> ct;
	cout << "---------------------PROBLEM 2---------------------" << endl;
	cout << "XX---MENU---XX" << endl;
	cout << "Input 1 : Insertion" << endl;
	cout << "Input 2 : Deletion" << endl;
	cout << "Input 3 : Display All leaf nodes" << endl;
	cout << "Input 4 : Get Height" << endl;
	cout << "Input 5 : Inorder print" << endl;
	cout << "Input 6 : Tickets sold for each train" << endl;
	cout << "Input -1 : End" << endl;
	int N = 0;
	while (N != -1)
	{
		cin >> N;
		if (N == 1)
		{
			string train_name;
			string train_no;
			string ticket_no;
			string cost;
			string passenger_id;
			cout << "To be inserted :-" << endl;
			cout << "Enter the Train's Name:-";
			cin >> train_name;
			cout << "Enter the Train number:-";
			cin >> train_no;
			cout << "Enter the ticket number:-";
			cin >> ticket_no;
			cout << "Enter the cost:-";
			cin >> cost;
			cout << "Enter the passenger id:-";
			cin >> passenger_id;
			root = insert(root, train_name, train_no, ticket_no, cost, passenger_id, ct);
			cout << "------------INSERTION COMPLETE------------" << endl;
		}
		if (N == 2)
		{
			cout << "To be deleted:-" << endl;
			string passenger_id;
			cout << "Enter the passenger id:-";
			cin >> passenger_id;
			root = remove(root, passenger_id, ct);
			cout << "------------DELETION COMPLETE------------" << endl;
		}

		if (N == 3)
		{
			cout << "The leaf Nodes are the following:-" << endl;
            cout<<left<<setw(15)<<setfill(' ') << "TRAIN NAME"
                <<setw(15)<<setfill(' ')             
				<<"TRAIN NO"
                <<setw(15)<<setfill(' ')
                <<"TICKET NO"
                <<setw(15)<<setfill(' ')
                <<"COST"
                <<setw(15)<<setfill(' ')
                <<"PASSENGER ID"
                <<setw(15)<<setfill(' ')<<endl;
            cout<<endl;
			display_leaf_node(root);
			cout << endl<<endl;
		}
		if (N == 4)
		{
			cout << "The height of the tree is:- ";
			cout << Height(root)<<endl;
			cout << "----------------------------" << endl<<endl;
		}
		if (N == 5)
		{
			cout<<"--------INORDER PRINT--------"<<endl;
            cout<< left<<setw(15)<< "TRAIN NAME"
                <<setw(15)<<setfill(' ')             
				<<"TRAIN NO"
                <<setw(15)<<setfill(' ')
                <<"TICKET NO"
                <<setw(15)<<setfill(' ')
                <<"COST"
                <<setw(15)<<setfill(' ')
                <<"PASSENGER ID"
                <<setw(15)<<setfill(' ')<<endl;
            cout<<endl;
			inorder_traversal(root);
			cout << endl;
		}
		if (N == 6)
		{
			cout<< "TRAIN"<<"		  "<<"TICKETS SOLD"<<endl;
			for (auto it : ct)
			{
				
				cout << it.first << ": " << it.second << endl;
			}
		}
	}

	return 0;
}