#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;
}