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.

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

Solution: If delete one node, then the root may change. And we need another pointer to track the parent node of target node. We have three situations to consider:

1. Delete node have no right subtree; (point parent left pointer to the node's left child);
2. Delete node have both right and left subtree; The new root will be the smallest in the right subtree
3. Delete leaf.

public TreeNode removeNode(TreeNode root, int value) {
    if(root == null) {
        return root;
    }
    TreeNode dummy = new TreeNode(-1);
    dummy.left = root;
    TreeNode parent = find(dummy, root, value);
    TreeNode node = null;
    if(parent.left != null && parent.left.val == value) {
        node = parent.left;
    }
    else if(parent.right != null && parent.right.val == value) {
        node = parent.right;
    }
    else {
        //no target found
        return dummy.left;
    }
    deleteNode(parent, node);
    //here can not return root, since root may be deleted.
    return dummy.left;
}

public TreeNode find(TreeNode parent, TreeNode root, int value) {
    if(root == null) {
        return parent;
    }
    if(root.val == value) {
        return parent;
    }
    if(root.val > value) {
        parent = root;
        return find(parent, root.left, value);
    }
    else {
        parent = root;
        return find(parent, root.right, value);
    }
}

public void deleteNode(TreeNode parent, TreeNode node) {
    if(node.right == null) {
        if(parent.left != null) {
            //delete node have no right subtree
            parent.left = node.left;
        }
        else {
            //delete leaf
            parent.left = null;
            parent.right = null;
        }
    }
    else {
        TreeNode temp = node.right;
        TreeNode father = node;

        while(temp.left != null) {
            father = temp;
            temp = temp.left;
        }
        if(father.left == temp) {
            father.left = temp.right;
        }
        else {
            father.right = temp.right;
        }
        if(parent.left == node) {
            parent.left = temp;
        }
        else {
            parent.right = temp;
        }
        temp.left = node.left;
        temp.right = node.right;
    }
}