**Binary Search Tree (BST):** A binary search tree is a hierarchical data structure in which each node has at most two children. It follows these properties: 1. The left subtree of a node contains only nodes with values less than the node's key. 2. The right subtree contains only nodes with values greater than the node's key. 3. Both left and right subtrees must also be binary search trees. **Example** ![Binary Search Tree](https://i.postimg.cc/jjkbWYDb/Screenshot-2025-03-25-171641.png) ### **C++ Program to Implement Insertion and Deletion in BST** ```cpp #include using namespace std; struct Node { int key; Node *left, *right; Node(int val) : key(val), left(NULL), right(NULL) {} }; // Function to insert a node in BST Node* insert(Node* root, int key) { if (root == NULL) return new Node(key); if (key < root->key) root->left = insert(root->left, key); else root->right = insert(root->right, key); return root; } // Function to find the minimum value node Node* minValueNode(Node* node) { Node* current = node; while (current && current->left != NULL) current = current->left; return current; } // Function to delete a node in BST Node* deleteNode(Node* root, int key) { if (root == NULL) return root; if (key < root->key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else { if (root->left == NULL) { Node* temp = root->right; delete root; return temp; } else if (root->right == NULL) { Node* temp = root->left; delete root; return temp; } Node* temp = minValueNode(root->right); root->key = temp->key; root->right = deleteNode(root->right, temp->key); } return root; } // Inorder traversal (Left, Root, Right) void inorder(Node* root) { if (root != NULL) { inorder(root->left); cout << root->key << " "; inorder(root->right); } } // Main function int main() { Node* root = NULL; root = insert(root, 50); root = insert(root, 30); root = insert(root, 70); root = insert(root, 20); root = insert(root, 40); root = insert(root, 60); root = insert(root, 80); cout << "Inorder traversal before deletion: "; inorder(root); cout << endl; root = deleteNode(root, 50); cout << "Inorder traversal after deletion: "; inorder(root); cout << endl; return 0; }