Remove Node in Binary Search Tree

[huimeich]

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

[huimeich]

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) {
        if (root==NULL) return root;
        if (root->val==value) return removeRoot(root);
        TreeNode* par=root;
        TreeNode* par2;
        TreeNode* temp=root;
        while(temp && temp->val != value) {
            par=temp;
            if (temp->val > value) temp=temp->left;
            else temp=temp->right;
        }
        if (temp==NULL) return root;
        par2=removeRoot(temp);
        if (par->val > value) par->left=par2;
        else par->right=par2;

        return root;        
    }
    TreeNode* removeRoot(TreeNode* root) {
        if (root->left==NULL) return root->right;
        TreeNode* par2;
        TreeNode* temp;
        temp=root->left; par2=root;
        while (temp->right) {par2=temp; temp=temp->right;}
        if (par2->val > temp->val) par2->left=temp->left;
        else par2->right=temp->left;
        temp->right=root->right;
        temp->left=root->left;
        return temp;
    }
};

[huimeich]

Need understand

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(0);
        dummy.left = root;

        TreeNode parent = findNode(dummy, root, value);
        TreeNode node;
        if (parent.left != null && parent.left.val == value) {
            node = parent.left;
        } else if (parent.right != null && parent.right.val == value) {
            node = parent.right;
        } else {
            return dummy.left;
        }

        deleteNode(parent, node);

        return dummy.left;
    }

    private TreeNode findNode(TreeNode parent, TreeNode node, int value) {
        if (node == null) {
            return parent;
        }

        if (node.val == value) {
            return parent;
        }
        if (value < node.val) {
            return findNode(node, node.left, value);
        } else {
            return findNode(node, node.right, value);
        }
    }

    private void deleteNode(TreeNode parent, TreeNode node) {
        if (node.right == null) {
            if (parent.left == node) {
                parent.left = node.left;
            } else {
                parent.right = node.left;
            }
        } 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;
        }
    }
}