#include using namespace std; struct Node { int data; Node* left; Node* right; Node(int value) : data(value), left(nullptr), right(nullptr) {} }; class BST { private: Node* root; Node* insert(Node* node, int key) { if (node == nullptr) return new Node(key); if (key < node->data) node->left = insert(node->left, key); else if (key > node->data) node->right = insert(node->right, key); return node; } Node* search(Node* node, int key) { if (node == nullptr || node->data == key) return node; if (key < node->data) return search(node->left, key); return search(node->right, key); } Node* findMin(Node* node) { while (node && node->left != nullptr) node = node->left; return node; } Node* deleteNode(Node* node, int key) { if (node == nullptr) return nullptr; if (key < node->data) { node->left = deleteNode(node->left, key); } else if (key > node->data) { node->right = deleteNode(node->right, key); } else { if (node->left == nullptr && node->right == nullptr) { delete node; return nullptr; } else 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; } else { Node* temp = findMin(node->right); node->data = temp->data; node->right = deleteNode(node->right, temp->data); } } return node; } void inorder(Node* node) { if (node == nullptr) return; inorder(node->left); cout << node->data << " "; inorder(node->right); } void destroy(Node* node) { if (node == nullptr) return; destroy(node->left); destroy(node->right); delete node; } public: BST() : root(nullptr) {} ~BST() { destroy(root); } void insert(int key) { root = insert(root, key); } bool search(int key) { return search(root, key) != nullptr; } void remove(int key) { root = deleteNode(root, key); } void inorder() { inorder(root); cout << endl; } }; int main() { BST tree; tree.insert(50); tree.insert(30); tree.insert(70); tree.insert(20); tree.insert(40); tree.insert(60); tree.insert(80); tree.inorder(); tree.remove(50); tree.inorder(); cout << (tree.search(60) ? "Found" : "Not found") << endl; }

Binary Search Tree and implementation in C++