Untitled

#include <iostream>

using namespace std;

class Node{
public:
	Node* left;
	int data;
	Node* right;

	Node(int value){
		data = value;
		left = right = nullptr;
	}
};

struct BinarySearchTree{
	Node* root;
	BinarySearchTree(){
		root = nullptr;
	}

private:
	//Insert a Node
	Node* insertHelper(Node* node, int key){
		if(node == nullptr){
			node = new Node(key);
			return node;
		}
		if(key < node->data){
			node->left = insertHelper(node->left, key);
		}
		else if(key > node->data){
			node->right = insertHelper(node->right, key);
		}
		return node;
	}

	//Search a Node
	Node* searchHelper(Node* node, int key){
		if(node == nullptr)
			return node;
		if(key < node->data){
			searchHelper(node->left, key);
		}
		else if(key > node->data){
			searchHelper(node->right, key);
		}
		else
			return node;
	}

	//Find the inorder successor
	Node* inorderSuccessor(Node* node){
		Node* current = node->right;

		//Find the leftmost leaf
		while(current && current->left){
			current = current->left;
		}

		return current;
	}

	//Delete a Node
	Node* deleteNodeHelper(Node* node, int key){
		if(node == nullptr)
			return node;

		//Find the node to be deleted
		if(key < node->data){
			node->left = deleteNodeHelper(node->left, key);
		}
		else if(key > node->data){
			node->right = deleteNodeHelper(node->right, key);
		}
		else{
			//If the node has only one child or no child
			if(node->left == nullptr){
				Node* temp = node->right;
				delete(node);
				return temp;
			}
			else if(node->right == nullptr){
				Node* temp = node->left;
				delete(node);
				return temp;
			}

			//If the node has two children
			Node* temp = inorderSuccessor(node);
			node->data = temp->data;
			node->right = deleteNodeHelper(node->right, temp->data);
		}
		return node;
	}

	//Inorder Traversal
	void inorderHelper(Node* node){
		if(node == nullptr)
			return;
		inorderHelper(node->left);
		cout << node->data << " ";
		inorderHelper(node->right);
	}

public:
	void insert(int key){
		root = insertHelper(root, key);
	}

	int search(int key){
		if(searchHelper(root, key) == nullptr)
			return 0;
		return 1;
	}

	void deleteNode(int key){
		deleteNodeHelper(root, key);
	}

	void inorder(){
		inorderHelper(root);
		cout << endl;
	}

};

BinarySearchTree BST;

int main()
{
	BST.insert(30);
	BST.insert(20);
	BST.insert(10);
	BST.insert(25);
	BST.insert(40);
	BST.insert(35);
	BST.insert(45);
	BST.insert(42);
	BST.insert(43);

	BST.deleteNode(20);
	BST.inorder();

	cout << BST.search(42) << endl;

	return 0;
}