when deleteing current node:

- change root to root->left and store root->right. then left and right subtree of current root remain same
- find right-most leaf of current root to insert previous stored root->right.

'''

class Solution {

public:

TreeNode* deleteNode(TreeNode* root, int key) {

if(!root) return NULL;

if (root->val == key) {

if (root->left) {

TreeNode * tmp = root->right;

root = root->left;

TreeNode *ptr = root;

while (ptr->right) {

ptr = ptr->right;

}

ptr->right = tmp;

}

else root = root->right;

return root;

}

if (key > root->val)

root->right = deleteNode(root->right, key);

else

root->left = deleteNode(root->left, key);

return root;

}

};

'''