```
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
//Base case: if root is null, or key is not found, return root
if(root==null)
return root;
//General case: to keep track of node where key is found and its parent
TreeNode prev=null;
TreeNode current=root;
boolean keyFound=false;
/*Check to see if key is present in tree,
if present, set keyFound to true an exit,
else based on key value recurse on left or right subtree */
while(current!=null)
{
if(current.val==key)
{
keyFound=true;
break;
}
prev=current;
if(key<current.val)
current=current.left;
else
current=current.right;
}
//if key is found
if(keyFound)
{
//Case 1: if key node is the root
if(current==root)
{
//if either subtree is null, return the other subtree as the root node
if(current.left==null)
return current.right;
if(current.right==null)
return current.left;
//if both subtrees are present, set right subtree as root and attach left subtree as left child of right subtree
TreeNode newRoot=current.right;
TreeNode iter=newRoot;
while(iter.left!=null)
{
iter=iter.left;
}
iter.left=current.left;
//set the newRoot as root node
root=newRoot;
}
//Case 2: if key node is an internal node
else
{
//Case 3a: if key node is left subtree of its parent
if(prev.left==current)
{
//if either subtree of key node is null, set other subtree as left child of parent node
if(current.left==null)
prev.left=current.right;
else if(current.right==null)
prev.left=current.left;
/*if both subtrees are present,set left subtree of keynode as left child of parent node
set right subtree of key node as right child of left subtree of key node */
else
{
TreeNode iter=current.left;
while(iter.right!=null)
{
iter=iter.right;
}
iter.right=current.right;
prev.left=current.left;
}
}
//Case 3b: if key node is right subtree of its parent
else if(prev.right==current)
{
//if either subtree of key node is null, set other subtree as left child of parent node
if(current.left==null)
prev.right=current.right;
else if(current.right==null)
prev.right=current.left;
/*if both subtrees are present,set right subtree of keynode as right child of parent node
set left subtree of key node as left child of right subtree of key node */
else
{
TreeNode iter=current.right;
while(iter.left!=null)
iter=iter.left;
iter.left=current.left;
prev.right=current.right;
}
}
}
}
//return root
return root;
}
}
```