Editing Binary Search Trees (section)

=== Deletion ===

To delete a value from a BST, we first search for the node containing the value. If the node has no children, we simply remove it. If the node has one child, we replace the node with its child. If the node has two children, we find the inorder successor (or predecessor) of the node, replace the node with the successor, and then delete the successor.

Example:

<pre>
Node* minValueNode(Node* node) {
    Node* current = node;

    while (current && current->left) {
        current = current->left;
    }

    return current;
}

Node* deleteNode(Node* root, int value) {
    if (root == nullptr) {
        return root;
    }

    if (value < root->data) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->data) {
        root->right = deleteNode(root->right, value);
    } else {
        if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        }

        Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }

    return root;
}
</pre>