# Easy iterative java solution with comments

• /**
* 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;

}
}

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