Delete Node in a BST

Solution 1(recursive):

TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == NULL) return NULL;
        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 == NULL)
                return root->right;
            if(root->right == NULL)
                return root->left;
            else{
                TreeNode* cur = root->right;
                while(cur->left) cur = cur->left;
                /*
                root->val = cur->val;
                root->right = deleteNode(root->right, root->val);
                */
                cur->left = root->left;
                return root->right;
            }
        }
        return root;
    }

root->val = cur->val;
root->right = deleteNode(root->right, root->val);
不完美，因为涉及到赋值和继续的递归。
cur->left = root->left;
return root->right;
完美，无赋值，直接返回，效率高。

Solution 2(iterative):

private TreeNode deleteRootNode(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null) {
            return root.right;
        }
        if (root.right == null) {
            return root.left;
        }
        TreeNode next = root.right;
        TreeNode pre = null;
        for(; next.left != null; pre = next, next = next.left);
        next.left = root.left;
        if(root.right != next) {
            pre.left = next.right;
            next.right = root.right;
        }
        return next;
    }
    
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode cur = root;
        TreeNode pre = null;
        while(cur != null && cur.val != key) {
            pre = cur;
            if (key < cur.val) {
                cur = cur.left;
            } else if (key > cur.val) {
                cur = cur.right;
            }
        }
        if (pre == null) {
            return deleteRootNode(cur);
        }
        if (pre.left == cur) {
            pre.left = deleteRootNode(cur);
        } else {
            pre.right = deleteRootNode(cur);
        }
        return root;
    }

先找到要删除的结点，然后调用 删除根 函数。
空间消耗少。

There are many solutions that got high votes using recursive approach, including the ones from the Princeton’s Algorithm and Data Structure book. Don’t you notice that recursive approach always takes extra space? Why not consider the iterative approach first?
Some solutions swap the values instead of swapping the nodes. In reality, the value of a node could be more complicated than just a single integer, so copying the contents might take much more time than just copying the reference.
As for the case when both children of the node to be deleted are not null, I transplant the successor to replace the node to be deleted, which is a bit harder to implement than just transplant the left subtree of the node to the left child of its successor. The former way is used in many text books too. Why? My guess is that transplanting the successor can keep the height of the tree almost unchanged, while transplanting the whole left subtree could increase the height and thus making the tree more unbalanced.