Remove Node in Binary Search Tree Show result

Remove Node in Binary Search Tree Show result

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

--------------- thinking -------------------------
BUG: remember to update parent info of a deleting node

A better solution here:
http://www.dailyfreecode.com/code/insert-delete-node-binary-search-tree-2843.aspx
--------------- codes --------------------------
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @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.
     */
    TreeNode* removeNode(TreeNode* root, int value) {
        // write your code here
        //find the node
        if (root == NULL) return root;
        TreeNode *parent = NULL;
        TreeNode *target = finder(root, value, parent);
        if (target == root && root->left == NULL && root->right == NULL) return NULL;
        if (target == NULL) return root;
        if (target->left == NULL && target->right == NULL) {
            if (parent->left == target) {
                parent->left = NULL;
            } else {
                parent->right = NULL;
            }
            return root;
        }
        remover(target, parent);
        return root;
    }
    TreeNode* finder(TreeNode* root, int value, TreeNode* &parent) {
        TreeNode *cur = root;
        parent = root;
        while (cur) {
            if (cur->val == value) {
                return cur;
            } else if (cur->val > value) {
                parent = cur;
                cur = cur->left;
            } else if (cur->val < value) {
                parent = cur;
                cur = cur->right;
            }
        }
        return NULL;
    }
    void remover(TreeNode* root, TreeNode* &parent) {
        if (root->left == NULL && root->right == NULL) {
            if (parent->left == root) {
                parent->left = NULL;
            } else {
                parent->right = NULL;
            }
            return;
        }
        parent = root;
        if (root->left) {
            TreeNode *rightmost = root->left;
            while (rightmost->right) {
                parent = rightmost;
                rightmost = rightmost->right;
            }
            root->val = rightmost->val;
            if (rightmost->left == NULL) {
                if (parent->left == rightmost) {
                    parent->left = NULL;
                } else {
                    parent->right = NULL;
                }
                return;
            } else {
                remover(rightmost, parent);
            }
        } else {
            TreeNode *leftmost = root->right;
            while (leftmost->left) {
                parent = leftmost;
                leftmost = leftmost->left;
            }
            root->val = leftmost->val;
            if (leftmost->right == NULL) {
                if (parent->left == leftmost) {
                    parent->left = NULL;
                } else {
                    parent->right = NULL;
                }
                return;
            } else {
                remover(leftmost, parent);
            }
        }
    }
};