Simplify corner cases via a dummy parent of the root


  • 3
    L

    We can quite simplify the logic by adding a dummy parent of the root. See the following concise iterative solution.

    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode dummyRoot = new TreeNode(0), x = root, p = dummyRoot;
        dummyRoot.left = root;
    
        while(x != null && x.val != key) {
            p = x;
            if (key < x.val) x = x.left;
            else x = x.right;
        }
        if (x != null && x.val == key) {
            if (x.left != null && x.right != null) {
                p = x;
                TreeNode y = x.right;
                for(; y.left != null; p = y, y = y.left); // empty for-body
                x.val = y.val;
                x = y; // Instead of deleting x, we delete y.
            }
    
            // Now, at least one child of x must be null.
            TreeNode child = x.left != null ? x.left : x.right;
            if (p.left == x) p.left = child;
            else p.right = child;
        }
        return dummyRoot.left;
    }
    

Log in to reply
 

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