Delete BST Node
    // find minimum in a tree. 
    Node* findMin(Node* root) {
        while(root->left != NULL) root = root->left;
        return root;
    }
 
    // delete a value from Binary Search tree.
    struct Node* delete(struct Node *root, int data) {
        if(root == NULL) {
            return root; 
        } else if (data < root->data) {
            root->left = delete(root->left,data);
        } else if (data > root->data) {
            root->right = delete(root->right,data);
        } else {                                             // found it
            if (root->left == NULL && root->right == NULL) { // case 1: No child
                delete root;
                root = NULL;
            } else if(root->left == NULL) {                  // case 2: One child 
                struct Node *temp = root;
                root = root->right;
                delete temp;
            } else if(root->right == NULL) {
                struct Node *temp = root;
                root = root->left;
                delete temp;
            } else {                                         // case 3: 2 children
                struct Node *temp = findMin(root->right);   
                root->data = temp->data;                     // just change the value, no need to really change node links
                root->right = delete(root->right,temp->data);// reuse delete() itself, this time will be case 1 or 2
            }
        }
        return root;
    }
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License