1

14kviews

Explain different cases for deletion of a node in binary search tree. Write function for each case.

**1 Answer**

1

14kviews

Explain different cases for deletion of a node in binary search tree. Write function for each case.

3

517views

written 2.2 years ago by | • modified 2.2 years ago |

- A
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.*Binary Search Tree (BST)* - Commonly performed operations on binary search trees are
*searching, insertion, and deletion.* - Here, we see
**Delete operation**in detail.

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

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

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

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

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;
// start with the root node
Node* cur = root;
// return if the key is not found in the tree
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;
}
```

ADD COMMENT
EDIT

Please log in to add an answer.