A straight forward solution for searching for the given key in a BST and deleting it.

```
TreeNode deleteNode(TreeNode root, int key){
//General sanity check and if you ever run into a null node, just turn back
if(root == null)
return root;
/*
* Check if the given key is lesser than the root's key, if yes, go down its left subtree
* else if the key is bigger than the root's key, then go down its right subtree
*/
if(key < root.val)
root.left = deleteNode(root.left, key);
else if(key > root.val)
root.right = deleteNode(root.right,key);
else{
//If you have reached the node that you're searching for, 2 conditions arise
//1. Suppose the node has 0 or 1 children
if(root.left ==null || root.right == null){
TreeNode temp = null;
//If there is not left subtree, assign the right subtree to the temp
if(root.left == null)
temp = root.right;
else
temp = root.left;
//Now rewrite the current node (which you wanted to delete) with its children
root = temp;
}else{
/*
* 2. Suppose the node has 2 children, then travel down its right subtree and
* get the next In-Order successor. Basically, get the smallest node
* in the current node's right subtree
*/
TreeNode next = getMin(root.right);
//Overwrite current node's key with the successor's key
root.val = next.val;
//Now delete the original successor from the right subtree
root.right = deleteNode(root.right, next.val);
}
}
return root;
}
/*
* Utility function to get the smallest node in a BST
*/
TreeNode getMin(TreeNode root){
if(root != null){
while(root.left != null)
root = root.left;
}
return root;
}
```