Difficulty: Medium, Asked-in: Google, Amazon, Qualcomm
Key takeaway: This is an excellent problem to learn pointer manipulation in binary trees and problem-solving using both iterative and recursive approaches.
Problem Statement: Given a binary search tree and a key value. Write a program to delete the given key from the BST and return the updated root node.
Examples
5 5
/ \ delete 2 / \
3 7 ---------> 3 7
/ \ / \ \ / \
2 4 6 8 4 6 8
5 5
/ \ delete 3 / \
3 7 ---------> 4 7
/ \ / \ / / \
2 4 6 8 2 6 8
5 6
/ \ delete 5 / \
3 8 ---------> 3 8
/ \ / \ / \ / \
2 4 6 9 2 4 7 9
\
7
To delete a node in a BST, we need to first search for that node. After this, we need to check if there are any nodes present in the left and right subtree of that node. If yes, then we need to appropriately link its subtrees back into the tree somewhere else. So, deletion is somewhat trickier than insertion.
Based on the above idea, the strategy for deleting a node from a binary search tree has three cases.
Case 1: Node to be deleted is a node with no children (leaf node)
We just delete that node from BST.
Case 2: Node to be deleted is a node with one child
There is one parent and one grandchild, so we can link the grandchild directly to the parent node and delete that node.
Case 3: Node to be deleted is a node with two children
This one is a little bit tricky because we have to follow three key steps:
Because that node has a right child, its in-order successor is the node with the smallest key in its right subtree (leftmost descendant in the right subtree). So this replacement will preserve the BST property because there are no keys between the node's key and the successor’s key.
Now, the critical question is: How can we implement this? We can use both recursive and iterative approaches to search for the key and perform the deletion. Let’s discuss them one by one.
Suppose we use a function called bstDeleteRecursive(root, k) to delete the node with key k in the binary search tree with a given root node.
Step 1: If key k is less than root->key, then k will be present in the left subtree. So we recursively call the same function for the left subtree to delete that node, i.e., root->left = bstDeleteRecursive(root->left, k). Here we set root->left with the node returned after the deletion in the left subtree.
Step 2: If key k is greater than root->key, then k will be present in the right subtree. So we recursively call the same function for the right subtree to delete that node, i.e., root->right = bstDeleteRecursive(root->right, k). Here we set root->right with the node returned after the deletion in the right subtree.
Step 3: If we find k == root->key, we need to perform operations to delete that node based on the above three cases.
Else if the root has only the right child, then we delete the root node and return its right child.
if (root->left == NULL and root->right == NULL)
{
free(root);
return NULL;
}
else if (root->left == NULL)
{
BSTNode* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
BSTNode* temp = root->left;
free(root);
return temp;
}
Else, the root has both left and right child: So, we find the inorder successor node, set the key of root with the key of the inorder successor, and delete the inorder successor. To find the inorder successor, we call findBSTMin(root->right) to find the node with the minimum key in the right subtree. To delete the inorder successor, we call deleteBSTMin(root->right) to delete the node with the minimum key in the right subtree.
BSTNode *temp = findBSTMin(root->right);
root->key = temp->key;
root->right = deleteBSTMin(root->right);
Step 4: Finally, we returns the root node of the modified binary search tree.
struct BSTNode
{
int key;
BSTNode *left;
BSTNode *right;
};
BSTNode* findBSTMin(BSTNode *node)
{
while (node->left != NULL)
node = node->left;
return node;
}
BSTNode* deleteBSTMin(BSTNode* node)
{
if (node == NULL)
return NULL;
if (node->left == NULL)
{
BSTNode* temp = node->right;
free(node);
return temp;
}
node->left = deleteBSTMin(node->left);
return node;
}
BSTNode* bstDeleteRecursive(BSTNode *root, int k)
{
if (root == NULL)
return NULL;
if (k < root->key)
root->left = bstDeleteRecursive(root->left, k);
else if (k > root->key)
root->right = bstDeleteRecursive(root->right, k);
else
{
if (root->left == NULL and root->right == NULL)
{
free(root);
return NULL;
}
else if (root->left == NULL)
{
BSTNode* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
BSTNode* temp = root->left;
free(root);
return temp;
}
BSTNode *temp = findBSTMin(root->right);
root->key = temp->key;
root->right = deleteBSTMin(root->right);
}
return root;
}
We can also implement the above idea iteratively. For this, we iteratively move down the tree to find the node with key k and perform various operations based on the above three cases to delete the node.
Step 1: We first traverse the BST iteratively to find the node with the key to be deleted. For this, we run a loop until either the key is found or the current node becomes NULL. During this process, we also keep track of the parent of the current node. Why are we doing this? Think for a while!
// curr will point to the key to be deleted.
BSTNode* curr = root;
// prev will point to parent of the key to be deleted.
BSTNode* prev = NULL;
//Check if key is present in BST.
while (curr != NULL && curr->key != k)
{
prev = curr;
if (k < curr->key)
curr = curr->left;
else
curr = curr->right;
}
Step 2: If the key is not found, we simply return the root node.
Step 3: Otherwise, if the current node has only one child or no child, we delete the node by redirecting the parent’s pointer to the current node’s child and deallocating the memory of the current node.
if (curr->left == NULL || curr->right == NULL)
{
// newNode will replace the node to be deleted.
BSTNode* newNode;
if (curr->left == NULL)
newNode = curr->right;
else
newNode = curr->left;
//Check if the node to be deleted is the root.
if (prev == NULL)
{
free(curr);
return newNode;
}
// Check if the node to be deleted is prev's left or
// right child and then replace this with newCurr.
if (curr == prev->left)
prev->left = newNode;
else
prev->right = newNode;
free(curr);
}
Step 4: If the current node has two children, we first find the inorder successor of the current node (the smallest value in the right subtree of the node), copies the value of the inorder successor to the current node, and deletes the inorder successor.
// temp will point to the inorder successor
BSTNode* temp;
// parent will point to the parent of inorder successor
BSTNode* parent = NULL;
// Now find the inorder successor
// This will be the node with minimum key in right subtree
temp = curr->right;
while (temp->left != NULL)
{
parent = temp;
temp = temp->left;
}
// Check if the parent of the inorder successor is the curr or not.
// If it isn't, then make the left child of its parent equal to the
// in-order successor's right child. Otherwiese, make the right child of the node
// to be deleted equal to the right child of the inorder successor.
if (parent != NULL)
parent->left = temp->right;
else
curr->right = temp->right;
curr->key = temp->key;
free(temp);
Step 5: Finally, we returns the root node of the modified binary search tree after deletion.
BSTNode* deleteBstIterative(BSTNode *root, int k)
{
BSTNode* curr = root;
BSTNode* prev = NULL;
while (curr != NULL && curr->key != k)
{
prev = curr;
if (k < curr->key)
curr = curr->left;
else
curr = curr->right;
}
// if key is not present in BST
if (curr == NULL)
return root;
if (curr->left == NULL || curr->right == NULL)
{
BSTNode* newNode;
if (curr->left == NULL)
newNode = curr->right;
else
newNode = curr->left;
if (prev == NULL)
{
free(curr);
return newNode;
}
if (curr == prev->left)
prev->left = newNode;
else
prev->right = newNode;
free(curr);
}
else
{
BSTNode* parent = NULL;
BSTNode* temp;
temp = curr->right;
while (temp->left != NULL)
{
parent = temp;
temp = temp->left;
}
if (parent != NULL)
parent->left = temp->right;
else
curr->right = temp->right;
curr->key = temp->key;
free(temp);
}
return root;
}
When key k is a node with no child or one child, we need to just search the node with key k and perform some constant time pointer manipulation operation. Suppose the height of the tree is h, then searching takes time O(h) in the worst case because we need to perform one comparison for each level. So the overall time complexity is O(h) + O(1) = O(h).
When key k is a node with two children, we need to perform three critical operations. Suppose the node to be deleted is present at level m.
From the above analysis, we can conclude that deletion in the BST will take O(h) time in the worst case. However, we need to observe one thing: the height (h) of the tree depends on its structure. So there could be two extreme situations:
The space complexity depends on the implementation.
If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.