Deletion

Deletion is more complicated than the two operations we mentioned before. There are also many different strategies for deletion. We are going to introduce one of them which minimizes the changes. Our solution is to replace the target node with a proper child. According to the number of its children, we should consider three different cases:

1. If the target node has no child, we can simply remove the node.
2. If the target node has one child, we can use its child to replace itself.
3. If the target node has two children, replace the node with its in-order successor or predecessor node and delete that node.

Time complexity: O(n)

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return NULL;

    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == NULL) {
            TreeNode *tmp = root->right;
            free(root);
            return tmp;
        } else if (root->right == NULL) {
            TreeNode *tmp = root->left;
            free(root);
            return tmp;
        }

        TreeNode *minNode = root->right;
        while (minNode->left) minNode = minNode->left;

        root->val = minNode->val;
        root->right = deleteNode(root->right, minNode->val);
    }

    return root;
}