"When you delete a node from the Binary Search Tree (BST), we must ensure that the left node is smaller than the root, and the root is smaller than the right node."

## Delete node (case 1: No child

Find the parent of the node you wish to delete, you need to remove its reference to the node you want to delete


Removing the leaf node, you don't need to consider the specific property of BST

## Delete node (case 2: one child

---

Connect to the sub children to ensure that the subtree won't disappear



## Delete node (case 3: two child

Trick case

- Find min in right
- copy its value to -> (you want to delete a node in its position)
- Delete duplication value in right sub tree


Delete 17


---


---

case 1


---

# Delete function

case 3



struct btNode* deleteNodeFromBST(struct btNode* rootPtr, int deleteData){
    if (rootPtr == NULL) return rootPtr; //terminated condiction  

    // Traverse Delte node position

    else if (deleteData < rootPtr->data ) rootPtr->left = deleteNodeFromBST(rootPtr->left,deleteData);
    else if (deleteData > rootPtr->data ) rootPtr->right = deleteNodeFromBST(rootPtr->right,deleteData);
    // deleteData = rootPtr->data
    else {
        // case 1: non child 
            if (rootPtr->left&&rootPtr->right){

                free(rootPtr);
                rootPtr = NULL;
                return  rootPtr;
                
            }

        // case 2 : one child

        if (rootPtr->right == NULL){
            struct btNode *temp = rootPtr;
            rootPtr = rootPtr->left;
            free(temp);
            return rootPtr;
        }
        else if (rootPtr->left == NULL){
            struct btNode *temp = rootPtr;
            rootPtr = rootPtr->right;
            free(temp);
            return rootPtr;
        }

        // case 3
        else {
            // find the min in right subtree
            struct btNode* temp = findMinRecusiveReturnAddress(rootPtr->right);

            rootPtr = temp->right;
            rootPtr->data = temp->data;
            rootPtr->right = deleteNodeFromBST(rootPtr->right,temp->data)  // it will return NULL (case 1)

        }
    }
    return rootPtr;
}