We will only do deletion when `root->val == NULL`

, so if `root->val > key`

we can know that the key is in the left subtree, then `root->left = deleteNode(root->left, key)`

, if `root->val < key`

should do `root->right = deleteNode(root->right, key)`

.

When `root->val == NULL`

we need to delete `root`

. If `root->left == NULL && root->right == NULL`

we can just delete root and return `NULL`

, else we can chose `root->left`

or `root->right`

to be the new `root`

in case it is not `NULL`

.

```
class Solution
{
public:
TreeNode* deleteNode(TreeNode* root, int key)
{
if(root == NULL) return NULL;
if(root->val == key)
{
if(root->right)
{
TreeNode* p = root->right;
while(p->left) p = p->left;
p->left = root->left;
return root->right;
}
else if(root->left)
return root->left;
else return NULL;
}
if(root->val > key)
root->left = deleteNode(root->left, key);
if(root->val < key)
root->right = deleteNode(root->right, key);
return root;
}
};
```