Deletion in Binary Search Tree
To delete the given node from the binary search tree(BST), we should follow the below rules.
1.Leaf Node
If the node is leaf (both left and right will be NULL), remove the node directly and free its memory.
Example
100 100
/ \ / \
50 200 delete(300) 50 200
/ \ /
150 300 150
2.Node with Right Child
If the node has only right child (left will be NULL), make the node points to the right node and free the node.
Example
100 100
/ \ / \
50 200 delete(200) 50 300
\
300
3.Node with Left Child
If the node has only left child (right will be NULL), make the node points to the left node and free the node.
Example
100 100
/ \ / \
50 200 delete(200) 50 150
/
150
4.Node has both left and right child
If the node has both left and right child,
1.find the smallest node in the right subtree. say min
2.make node->data = min
3.Again delete the min node.
Example
(step 2) (step 3)
100 100 100
/ \ / \ / \
50 200 delete(200) 50 300 50 300
/ \ (right subtree min = 300) / \ /
150 300 (step 1) 150 300 150
Remove function with algorithm explanation
struct node *removeNode(struct node *root, int val) { /* * If the node becomes NULL, it will return NULL * Two possible ways which can trigger this case * 1. If we send the empty tree. i.e root == NULL * 2. If the given node is not present in the tree. */ if(root == NULL) return NULL; /* * If root->key < val. val must be present in the right subtree * So, call the above remove function with root->right */ if(root->key < val) root->right = removeNode(root->right,val); /* * if root->key > val. val must be present in the left subtree * So, call the above function with root->left */ else if(root->key > val) root->left = removeNode(root->left,val); /* * This part will be executed only if the root->key == val * The actual removal starts from here */ else { /* * Case 1: Leaf node. Both left and right reference is NULL * replace the node with NULL by returning NULL to the calling pointer. * free the node */ if(root->left == NULL && root->right == NULL) { free(root); return NULL; } /* * Case 2: Node has right child. * replace the root node with root->right and free the right node */ else if(root->left == NULL) { struct node *temp = root->right; free(root); return temp; } /* * Case 3: Node has left child. * replace the node with root->left and free the left node */ else if(root->right == NULL) { struct node *temp = root->left; free(root); return temp; } /* * Case 4: Node has both left and right children. * Find the min value in the right subtree * replace node value with min. * And again call the remove function to delete the node which has the min value. * Since we find the min value from the right subtree call the remove function with root->right. */ else { int rightMin = getRightMin(root->right); root->key = rightMin; root->right = removeNode(root->right,rightMin); } } //return the actual root's address return root; }
Implementation of Binary Search Tree Deletion (Recursive)
/* * Program : Binary Search Tree Deletion * Language : C */ #include<stdio.h> #include<stdlib.h> struct node { int key; struct node *left; struct node *right; }; struct node *getNewNode(int val) { struct node *newNode = malloc(sizeof(struct node)); newNode->key = val; newNode->left = NULL; newNode->right = NULL; return newNode; } struct node *insert(struct node *root, int val) { if(root == NULL) return getNewNode(val); if(root->key < val) root->right = insert(root->right,val); else if(root->key > val) root->left = insert(root->left,val); return root; } int getRightMin(struct node *root) { struct node *temp = root; //min value should be present in the left most node. while(temp->left != NULL){ temp = temp->left;} return temp->key; } struct node *removeNode(struct node *root, int val) { /* * If the node becomes NULL, it will return NULL * Two possible ways which can trigger this case * 1. If we send the empty tree. i.e root == NULL * 2. If the given node is not present in the tree. */ if(root == NULL) return NULL; /* * If root->key < val. val must be present in the right subtree * So, call the above remove function with root->right */ if(root->key < val) root->right = removeNode(root->right,val); /* * if root->key > val. val must be present in the left subtree * So, call the above function with root->left */ else if(root->key > val) root->left = removeNode(root->left,val); /* * This part will be executed only if the root->key == val * The actual removal starts from here */ else { /* * Case 1: Leaf node. Both left and right reference is NULL * replace the node with NULL by returning NULL to the calling pointer. * free the node */ if(root->left == NULL && root->right == NULL) { free(root); return NULL; } /* * Case 2: Node has right child. * replace the root node with root->right and free the right node */ else if(root->left == NULL) { struct node *temp = root->right; free(root); return temp; } /* * Case 3: Node has left child. * replace the node with root->left and free the left node */ else if(root->right == NULL) { struct node *temp = root->left; free(root); return temp; } /* * Case 4: Node has both left and right children. * Find the min value in the right subtree * replace node value with min. * And again call the remove function to delete the node which has the min value. * Since we find the min value from the right subtree call the remove function with root->right. */ else { int rightMin = getRightMin(root->right); root->key = rightMin; root->right = removeNode(root->right,rightMin); } } //return the actual root's address return root; } /* * it will print the tree in ascending order */ void inorder(struct node *root) { if(root == NULL) return; inorder(root->left); printf("%d ",root->key); inorder(root->right); } int main() { /* 100 / \ 50 200 / \ 150 300 */ struct node *root = NULL; root = insert(root,100); root = insert(root,50); root = insert(root,200); root = insert(root,150); root = insert(root,300); printf("Initial tree :\t"); inorder(root); printf("\n"); /* remove leaf node 300 100 / \ 50 200 / 150 */ root = removeNode(root,300); printf("After deletion of 300, the new tree :\t"); inorder(root); printf("\n"); /* remove root node 100 150 / \ 50 200 */ root = removeNode(root,100); printf("After deletion of 100, the new tree :\t"); inorder(root); printf("\n"); return 0; }