# An easy-understanding O(h) time, O(1) space Java solution.

• If the node is found, delete the node.
We need a function `deleteRoot` to delete the root from a BST.

• If `root==null`, then return `null`
• If `root.right==null`, then return `root.left`
• If `root.right!=null`, the the new root of the BST is root.right; And what we should do is to put root.left into this new BST. As all nodes in root.left is smaller than the new tree, we just need to find the left-most node.
``````public class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root==null || root.val==key) return deleteRoot(root);
TreeNode p=root;

while (true) { // search the node
if (key>p.val) {
if (p.right==null || p.right.val==key) {
p.right=deleteRoot(p.right);
break;
}
p=p.right;
}
else {
if (p.left==null || p.left.val==key) {
p.left=deleteRoot(p.left);
break;
}
p=p.left;
}
}
return root;
}

private TreeNode deleteRoot(TreeNode root) {
if (root==null) return null;
if (root.right==null) return root.left;
TreeNode x=root.right; // root.right should be the new root
while (x.left!=null) x=x.left; // find the left-most node
x.left=root.left;
return root.right;
}
}
``````

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