```
// Binary search for the interested node and if it
// 1. is a leaf node - easy, just delete it
// 2. only has right subtree - delete it and bring the right subtree to its place
// 3. only has left subtree - delete it and bring the left subtree to its place
// 4. has both subtrees - find the min node in the right subtree, swap it with this node and call deleteNode() again
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) {
} else 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) {
return root->right;
} else if (!root->right) {
return root->left;
} else {
root->val = getMin(root->right);
root->right = deleteNode(root->right, root->val);
}
}
return root;
}
int getMin(TreeNode* root) {
int ret = 0;
while (root) {
ret = root->val;
root = root->left;
}
return ret;
}
```