Remove Node in Binary Search Tree

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.

Solution:

Remove node in binary search tree:

1. Find the parent of the node that needs to be removed
2. Remove the node and connect its children to its parent:
   1. If this node only has one child, add this child to parent
   2. if this node has two children, replace this node with the left most node of its right subtree.

Code:

public class Solution {

    public TreeNode removeNode(TreeNode root, int value) {
        TreeNode dummy = new TreeNode(Integer.MIN_VALUE);
        dummy.left = root;

        TreeNode[] nodes = findParent(dummy, root, value);
        TreeNode parent = nodes[0];
        TreeNode node = nodes[1];
        if (node == null) {
            return dummy.left;
        }
        deleteNode(parent, node);
        return dummy.left;
    }

    private void deleteNode(TreeNode parent, TreeNode node) {
        if (node.right == null) {
            setParent(parent, node, node.left);
        } else {
            if (node.left == null) {
                setParent(parent, node, node.right);
                return;
            }
            TreeNode cur = node.right;
            TreeNode pre = cur;
            while (cur.left != null) {
                pre = cur;
                cur = cur.left;
            }
            pre.left = cur.right;
            cur.right = node.right;
            cur.left = node.left;
            setParent(parent, node, cur);
        }
    }

    private void setParent(TreeNode parent, TreeNode node, TreeNode newNode) {
        if (parent.left == node) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }
    }

    private TreeNode[] findParent(TreeNode parent, TreeNode node, int value) {
        if (node == null || node.val == value) {
            return new TreeNode[] {parent, node};
        }
        if (value < node.val) {
            return findParent(node, node.left, value);
        }  else {
            return findParent(node, node.right, value);
        }
    }
}