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


  • 8
    C

    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;
        }
    }
    

Log in to reply
 

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