---
# System prepended metadata

title: Delete a node from binary search tree

---



"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


![](https://hackmd.io/_uploads/Bku40tvc3.png)

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

![](https://hackmd.io/_uploads/rJy3k9Dq2.png)


![](https://hackmd.io/_uploads/S1UNZ9vq3.png)

## 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 

![](https://hackmd.io/_uploads/BJ0RXqPqh.png)

Delete 17

![](https://hackmd.io/_uploads/rJSgNqvc2.png)

---

![](https://hackmd.io/_uploads/BJlZVcw5h.png)

---

case 1 

![](https://hackmd.io/_uploads/BJwfEcwq3.png)


---

# Delete function 

case 3 
![](https://hackmd.io/_uploads/rJzZ-iDcn.png)


![](https://hackmd.io/_uploads/Byz1bsPch.png)


![](https://hackmd.io/_uploads/SJBMZivq2.png)


```cpp=

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;
}

```