```
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
return rec(root, key);
}
TreeNode* rec(TreeNode *root, int key)
{
if(!root)return nullptr; \\standard guard
if(root -> val < key) root -> right = rec(root -> right, key); \\search right
if(root -> val > key) root -> left = rec(root -> left, key); \\search left.
if(root -> val == key) \\ when found we check all cases. if left, if right, if both, if none.
{
if(!root -> left && !root -> right) return NULL;
if(!root -> left) return root -> right;
if(!root -> right)return root -> left;
if(root -> left && root -> right) \\ when both exist, we cannot simply delete. we need to move the lowest value at the right tree to the current position as it is the only one that will satisfy.
{
auto* mnvl = [](TreeNode* root) -> TreeNode* {while(root -> left) root = root -> left; return root;}(root -> right); \\simple left traversal to find the lowest val.
root -> val = mnvl -> val;
root -> right = rec(root -> right, mnvl -> val) ; \\ since the mininmum value is not at the root, we need to delete this min value. It happens in O(h).
return root;
}
}
return root;
}
};
```