# Non-recursive Java Algorithm, 7ms

• ``````/**
* 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) {
TreeNode cur = root, pre = null;

while(cur!=null && cur.val!=key) {
if(cur.val < key) {
pre = cur;
cur = cur.right;
} else {  // cur.val > key
pre = cur;
cur = cur.left;
}
}

if(cur == null) {
return root;
} else if(cur.right == null) {
if(pre == null) {
return cur.left;
} else {
if(pre.left == cur) {
pre.left = cur.left;
} else {
pre.right = cur.left;
}
return root;
}
} else {
TreeNode cur1 = cur.right, pre1 = null;

while(cur1!=null && cur1.left!=null) {
pre1 = cur1;
cur1 = cur1.left;
}

if(pre1 != null) {
pre1.left = cur1.right;
cur1.right = cur.right;
}
cur1.left = cur.left;
if(pre == null) {
return cur1;
} else {
if(pre.left == cur) {
pre.left = cur1;
} else {
pre.right = cur1;
}
return root;
}
}
}
}
``````

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