1
14kviews
Explain different cases for deletion of a node in binary search tree. Write function for each case.
3
517views

## Binary search tree (BST)

• A Binary Search Tree (BST) is a special type of tree where the value of the left child node’s always less than the parent node and the value of the right child node is greater than the parent node.
• Commonly performed operations on binary search trees are searching, insertion, and deletion.
• Here, we see Delete operation in detail.

## Delete Operation

• In a binary search tree, the Delete function is used to delete the specified node.
• But, delete a node from a binary search tree in such a way, that the property of the binary search tree doesn't violate.
• To achieve this there are three methods for deleting a node from a binary search tree are used.

Method - 1: Deletion of A Node Having No Child (Leaf Node)

Method - 2: Deletion of A Node Having Only One Child Node

Method - 3: Deletion of A Node Having Two Children Nodes

## Method - 1: Deletion of A Node Having No Child (Leaf Node)

• It is the simplest method when deleting a node is the leaf node.
• In this, the leaf node with is replaced the NULL and simply free the allocated space.
• Consider the following example where leaf node with value = 30 is deleted from the BST:

## Method - 2: Deletion of A Node Having Only One Child Node

• In this, replace the node that is going to be deleted with its only child node and then delete the child node, which now contains the value which is to be deleted.
• Replace it with the NULL and free the allocated space.
• Consider the following example where the node with one child node whose value = 25 is deleted from the BST:

## Method - 3: Deletion of A Node Having Two Children Nodes

• It is a quite complex method case compared to the other two methods.
• In this, the node which is to be deleted is replaced with its in-order successor or predecessor recursively until the node to be deleted is replaced on the leaf of the tree.
• After this, replace the node with NULL and free the allocated space. Consider the following example where the node with two child nodes whose value = 60 is deleted from the BST:

In-order Traversal Sequence of the following Tree is 15, 25, 30, 60, 65, 75, 85, 90, 95.

A node with two children can be deleted from the BST in the following two ways:

Way 1:

• Visit the right subtree of the deleting node.
• Take the least value node called the in-order successor node.
• Replace the deleting node with its in-order successor node.
• In this way take the node with value 65 which is the least valued in-order successor node of node 60 that is to be deleted.

Way 2:

• Visit the left subtree of the deleting node.
• Take the greatest value node called the in-order predecessor node.
• Replace the deleting node with its in-order predecessor node.
• In this way take the node with value 30 which is the greatest valued in-order predecessor node of the node 60 that is to be deleted.

## Function For Deletion in BST

Each of the methods mentioned above can be implemented as follows:

// Function to delete a node from a BST
void deletion(Node*& root, int item)
{
// pointer to store the parent of the current node
Node* parent = NULL;

Node* cur = root;

search(cur, item, parent);
if (cur == NULL)
return;

// Method 1: when node to be deleted has no children,means it is a leaf node
if (cur->left == NULL && cur->right == NULL)
{
// if the node to be deleted is not a root node, then set its
// parent left/right child to null
if (cur != root)
{
if (parent->left == cur)
parent->left = NULL;
else
parent->right = NULL;
}
// if the tree has only a root node, set it to null
else
root = NULL;

// deallocate the memory
free(cur);               // or delete curr;
}
// Method 3: when node to be deleted has two children
else if (cur->left && cur->right)
{
// find its inorder successor node
Node* succ  = findMinimum(cur- >right);

// find its inorder successor node
int val = succ->data;

// recursively delete the successor. Note that the successor
// will have at most one child (right child)
deletion(root, succ->data);

// copy value of the successor to the current node
cur->data = val;
}
// Method 2: when node to be deleted has only one child
else
{
// choose a child node
Node* child = (cur->left)? Cur- >left: cur->right;

// if the node to be deleted is not a root node, set its parent
// to its child
if (cur != root)
{
if (cur == parent->left)
parent->left = child;
else
parent->right = child;
}

// if the node to be deleted is a root node, then set the root to the child
else
root = child;

// deallocate the memory
free(cur);
}
}

// Helper function to find minimum value node in the subtree rooted at curr
Node* findMinimum(Node* cur)
{
while(cur->left != NULL) {
cur = cur->left;
}
return cur;
}