Untitled

//============================================================================
// Name        : 21142_MOCK.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
//Binary search tree
#include <iostream>
#include <stack>
using namespace std;

class BST;
class Node {
	int data;
	Node *left;
	Node *right;
public:
	friend class BST;
	Node(int x) {
		this->data = x;
		this->left = nullptr;
		this->right = nullptr;
	}
	Node() {
		this->data = -1;
		this->left = nullptr;
		this->right = nullptr;
	}
} *head = nullptr;

class BST {
public:
	friend class Node;
	Node* inPred(Node *x) {
		Node *tail = nullptr;
		if (x != nullptr) {
			while (x->right != nullptr) {
				tail = x;
				x = x->right;
			}
		}
		if (x != nullptr) {
			if (x->left == nullptr || x->right == nullptr) {
				if (tail->left == x)
					tail->left = nullptr;
				if (tail->right == x)
					tail->right = nullptr;
			}
		}
		return x;
	}
	void create();
	void deleteNode();
	Node* inorder(Node*);
	Node* preorder(Node*);
	Node* postorder(Node*);
} *bst = NULL;

void BST::create() {
	Node *temp = nullptr;
	int x;
	if (head == nullptr) {
		cout << "\nENter head's data: ";
		cin >> x;
		head = new Node(x);
		return;
	}
	cout << "\nENter data: ";
	cin >> x;
	temp = new Node(x);
	Node *s = head;
	Node *tail = nullptr;
	while (s != nullptr) {
		tail = s;
		if (temp->data < s->data) {
			s = s->left;
		} else if (temp->data > s->data) {
			s = s->right;
		} else {
			cout << "\nDuplicate Node\n";
			return;
		}
	}
	if (temp->data < tail->data)
		tail->left = temp;
	else
		tail->right = temp;
}

Node* BST::inorder(Node *x) {
	if (x != nullptr) {
		if (x->left != nullptr)
			x->left = inorder(x->left);
		if (x != nullptr && x->data != 0 && x->data != 1)
			cout << x->data << ", ";
		if (x->right != nullptr)
			x->right = inorder(x->right);
	}
	return x;
}

Node* BST::preorder(Node *x) {
	if (x != nullptr) {
		if (x != nullptr)
			cout << x->data << ", ";
		if (x->left != nullptr)
			x->left = inorder(x->left);
		if (x->right != nullptr)
			x->right = inorder(x->right);
	}
	return x;
}

Node* BST::postorder(Node *x) {
	if (x != nullptr) {
		if (x->left != nullptr)
			x->left = inorder(x->left);
		if (x->right != nullptr)
			x->right = inorder(x->right);
		if (x != nullptr)
			cout << x->data << ", ";
	}
	return x;
}

void BST::deleteNode() {
	int x;
	cout << "\nEnter data you want to delete: ";
	cin >> x;
	Node *temp = head;
	Node *tail = nullptr;
	while (temp != nullptr) {
//		tail = temp;
		if (x < temp->data) {
			tail = temp;
			temp = temp->left;
		} else if (x > temp->data) {
			tail = temp;
			temp = temp->right;

		} else
			break;
	}
	if (temp == nullptr) {
		cout << "\nNOT FOUND";
		return;
	}
	if (temp->left == nullptr && temp->right == nullptr) {
		if (tail->left == temp)
			tail->left = nullptr;
		if (tail->right == temp)
			tail->right == nullptr;
		delete temp;
		temp = nullptr;
		return;
	}
	Node *pred = inPred(temp->left);
	while (pred != nullptr) {
		temp->data = pred->data;
		temp = pred;
//		if (pred->left != nullptr)
			pred = inPred(pred->left);
	}
	delete temp;
	temp = nullptr;
}

int main() {
	bool menu = 1;
	bst = new BST();
	while (menu) {
		int ch;
		cout
				<< "\n\nMENU\n1.Insert\n2.Delete\n3.Traversals\nENTER YOUR CHOICE: ";
		cin >> ch;
		switch (ch) {
		case 1:
			bst->create();
			break;

		case 2:
			bst->deleteNode();
			break;

		case 3:
			cout << "\nINORDER- ";
			bst->inorder(head);
			cout << "\nPREORDER- ";
			bst->preorder(head);
			cout << "\nPOSTORDER- ";
			bst->postorder(head);
			break;

		case -1:
			menu = 0;
			break;

		default:
			break;
		}
	}
	return 0;
}