I see a lot of C++ solutions with memory leaks.

Here is a soln that does the following:

- uses recursion to find the node with key as its val.
- If key if found in a node without a right subtree, then we store the left subtree over as replacement.
- If key is found in a node with a valid right subtree, we use a two pointer strategy to find min, and later swap and delete the node with key val.

```
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root)
return root;
if (root->val == key) {
if (!root->right) {
TreeNode* left = root->left;
delete root;
return left;
} else {
//find the min in the right tree, swap and bubble out
TreeNode* minNode = root->right;
TreeNode* prevMinNode = nullptr;
while(minNode->left) {
prevMinNode = minNode;
minNode = minNode->left;
}
swap(minNode->val, root->val);
if (prevMinNode)
prevMinNode->left = minNode->right;
else
root->right = minNode->right;
delete minNode;
return root;
}
} else if (key < root->val)
root->left = deleteNode(root->left, key);
else
root->right = deleteNode(root->right, key);
return root;
}
```