1
16kviews
Explain different cases for deletion of a node in binary search tree. Write function for each case.
1 Answer
written 2.9 years ago by | • modified 2.9 years ago |
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
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:
Way 2:
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;
}