Remove Node in Binary Search Tree

Problem

Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You should keep the tree still a binary search tree after removal.

Example

Given binary search tree:

    5
   / \
  3   6
 / \
2   4

Remove 3, you can either return:

    5
   / \
  2   6
   \
    4

or

    5
   / \
  4   6
 /
2

Code - Java

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *   public int val;
 *   public TreeNode left, right;
 *   public TreeNode(int val) {
 *     this.val = val;
 *     this.left = this.right = null;
 *   }
 * }
 */
public class Solution {
    /**
     * @param root:  The root of the binary search tree.
     * @param value: Remove the node with given value.
     * @return: The root of the binary search tree after removal.
     */
    public TreeNode removeNode(TreeNode root, int value) {
        TreeNode dummy = new TreeNode(Integer.MAX_VALUE);
        dummy.left = root;

        TreeNode node = dummy;
        while (true) {
            if (node == null) break;

            if (node.left != null && node.left.val == value) {
                remove(node, true);
                break;
            } else if (node.right != null && node.right.val == value) {
                remove(node, false);
                break;
            } else {
                if (value < node.val) node = node.left;
                else node = node.right;
            }
        }
        return dummy.left;
    }

    private void remove(TreeNode parent, boolean isLeft) {
        TreeNode target = isLeft ? parent.left : parent.right;

        if (target.left == null && target.right == null) {
            if (isLeft) parent.left = null;
            else parent.right = null;
        } else if (target.left != null && target.right == null) {
            if (isLeft) parent.left = target.left;
            else parent.right = target.left;
        } else if (target.left == null && target.right != null) {
            if (isLeft) parent.left = target.right;
            else parent.right = target.right;
        } else {
            if (target.left.left == null && target.left.right == null) {
                target.val = target.left.val;
                target.left = null;
            } else {
                // inorder
                TreeNode newParent = target.left;
                while (newParent.right.right != null) {
                    newParent = newParent.right;
                }
                target.val = newParent.right.val;
                remove(newParent, false);
            }
        }
    }
}