gistfile1.txt

Node* BinarySearchTree::deleteKey(Node *root, int key) {
    if (!root) return root;
    
    if (key < root->val) {
        // If the key to be deleted is smaller than the root's key, then it lies in left subtree
        root->left = deleteKey(root->left, key);
    } else if (key > root->val) {
        // If the key to be deleted is greater than the root's key, then it lies in right subtree
        root->right = deleteKey(root->right, key);
    } else {
        // Node with only one child or no child
        if (!root->left) {
            Node *temp = root->right;
            free(root);
            return temp;
        } else if (!root->right) {
            Node *temp = root->left;
            free(root);
            return temp;
        }
        
        // Node with two children: get the inorder successor
        Node *temp = minNode(root->right);
        
        // Copy the inorder successor's content to this node
        root->val = temp->val;
        
        // Delete the inorder successor
        root->right = deleteKey(root->right, temp->val);
    }
    
    return root;
}