```
TreeNode *deleteNode(TreeNode *root, int key) {
if (!root) return NULL;
if (root->val < key) root->right = deleteNode(root->right, key); // search right child
else if (root->val > key) root->left = deleteNode(root->left, key); // search left child
else if (!root->right) { // node to be deleted has no right child
TreeNode *left = root->left;
delete root;
return left;
} else { // node to be deleted has right child, delete the min on the right side
TreeNode *pre = root, *right = root->right;
while (right->left) {
pre = right;
right = right->left;
}
root->val = right->val;
if (pre == root) pre->right = right->right;
else pre->left = right->right;
delete right;
}
return root;
}
```