# Yet another C++ soln without memory leak O(h) time.

• 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;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.