450. Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.

2. If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

// Recursion
TreeNode* deleteNode(TreeNode* root, int key) { // time: O(n); space: O(n)
    if (!root) return nullptr;
    if (root->val < key) 
        root->right = deleteNode(root->right, key);
    else if (root->val > key) 
        root->left = deleteNode(root->left, key);
    else {
        if (!root->left) {
            TreeNode* right = root->right;
            delete root;
            root = right;
        } else if (!root->right) {
            TreeNode* left = root->left;
            delete root;
            root = left;
        } else {
            TreeNode* cur = root->right;
            while (cur->left) cur = cur->left;
            root->val = cur->val;
            root->right = deleteNode(root->right, cur->val);
        }
    }
    return root;
}

// Recursion
TreeNode* deleteNode(TreeNode* root, int key) { // time: (n); space: O(n)
    if (!root) return nullptr;
    if (root->val == key) {
        if (!root->right) {
            TreeNode* left = root->left;
            delete root;
            return root = left;
        } else {
            TreeNode* right = root->right;
            while (right->left) right = right->left;
            swap(root->val, right->val);
        }
    }
    root->left = deleteNode(root->left, key);
    root->right = deleteNode(root->right, key);
    return root;
}

// Iteration
TreeNode* del(TreeNode* node) {
    if (!node->left && !node->right) return nullptr; // node is leaf
    if (!node->left || !node->right) return node->left ? node->left : node->right; // no left substree or no right subtree
    TreeNode *prun = node, *run = node->right;
    while (run->left) { // find the successor
        prun = run;
        run = run->left;
    }
    node->val = run->val; // replace the target value with the value of successor
    (prun == node ? node->right : prun->left) = run->right;
    return node;
}
TreeNode* deleteNode(TreeNode* root, int key) { // time: O(n); space: O(1)
    TreeNode* node = root, *prev = nullptr;
    while (node) {
        if (node->val == key) break;
        prev = node;
        if (node->val > key) node = node->left;
        else node = node->right;
    }
    if (!node) return root; // node is not found
    if (!prev) return del(root); // node is root
    if (prev->left && prev->left->val == key) {
        prev->left = del(prev->left);
    } else {
        prev->right = del(prev->right);
    }
    return root;
}