Introduction
A. J. Perlis and C. Thornton proposed a new version of a binary tree called “Threaded Binary Tree” that uses NULL pointers to improve its traversal process. In a threaded binary tree, NULL pointers are replaced by references of other nodes in the tree. These extra references are called threads.
Although threads can be deleted in any binary tree, it is most efficient to delete threads in a binary search tree or its variants, i.e. a tree that meets the Binary Search Tree properties. As a result, the Threaded Binary Tree we will use in this blog is a Binary Search Tree having Threads (threaded binary search tree).
Node Structure of Threaded Binary tree
struct Node{
int data;
Node *left, *right;
// false if the right pointer points to inorder successor
bool rightThread;
// false if the left pointer points to inorder predecessor
bool leftThread;
};
Before moving directly to Deletion in the Threaded Binary Search Tree, let us first look at the basics of the Threaded Binary Tree.
Deletion in Threaded Binary Search Tree
For deletion in the Threaded Binary Search Tree, we will first search the value to be deleted, and then we will see the possible cases for deleting the node in which the value is present.
// For deleting the value from threaded BST with the given root
// and returning a new root of BST
struct Node* dThreadedBST(struct Node* root, int value)
{
// Function for initializing the parent node to NULL and current node to root.
struct Node *parent = NULL, *current = root;
// Set true if value is found
int found = 0;
// Now, we will search value in BST
while (current != NULL) {
if (value == current->data) {
found = 1;
break;
}
parent = current;
if (value < current->data) {
if (current->leftThread == false)
current = current->left;
else
break;
}
else {
if (current->rightThread == false)
current = current->right;
else
break;
}
}
if (found == 0)
printf("The value is not present in tree\n");
// When the node to be deleted has two children
else if (current->leftThread == false && current->rightThread == false)
root = case3(root, parent , current);
// When the node to be deleted has only left child
else if (current->leftThread == false)
root = case2(root, parent , current);
// When the node to be deleted has only right child
else if (current->rightThread == false)
root = case2(root, parent , current);
// When a leaf node needs to be deleted
else
root = case1(root, parent , current);
return root;
}
We can use the delete operation to remove a node from a threaded binary search tree. However, there are three cases for removing it.
Case 1: When a leaf node needs to be deleted
When deleting a leaf Node in BST, the left or right pointer of the parent node is set to NULL. Whereas in Threaded binary search trees, it is turned into a thread instead of setting the pointer to NULL.
If the leaf Node is the left child of its parent, then after deletion, the parent’s left pointer should become a thread referring to its predecessor.
Let’s understand this using an example.
In the tree given above, if we delete node 18, then the left pointer of its parent node, node 20, will point to its predecessor node 15 (as shown below).
Similarly, If the leaf Node is the right child of its parent, then after deletion, the parent’s right pointer should become a thread referring to its successor. After deletion, the Node that was the in-order successor of the leaf Node will now become the in-order successor of the parent Node.
Now, let’s have a look at the code:
// Here, 'parent ' is a pointer referring to the parent node
// and 'current' is a pointer to the current node.
struct Node* case1 (struct Node* root, struct Node* parent, struct Node* current)
{
// If root node has to be deleted
if (parent == NULL)
root = NULL;
// If the node to be deleted is left child of its parent
else if (current == parent ->left) {
parent ->leftThread = true;
parent ->left = current->left;
}
// If the node to be deleted is the right child of its parent
else {
parent ->rightThread = true;
parent ->right = current->right;
}
// Now memory is freed, and new root is returned
free(current);
return root;
}
Case 2: When the node to be deleted has only one child
After deleting the Node like in a BST the inorder successor and predecessor of the Node are found.
s = inSucc(current);
p = inPred(current);
If Node to be deleted has a left subtree, then after deletion, the right thread of its predecessor should point to its successor.
Let’s understand this using an example.
In the figure given above, node 24 has node 23 as its predecessor and node 30 as its successor. So, after deleting node 24, node 30 becomes the successor of node 23, so the right thread of 23 will point to 30 (as shown in the figure given below).
Similarly, if Node to be deleted has a right subtree, then after deletion, the left thread of its successor should point to its predecessor.
Now, let’s have a look at the code:
// Here, 'parent ' is a pointer referring to the parent node
// and 'current' is a pointer to the current node.
struct Node* case2 (struct Node* root, struct Node* parent, struct Node* current)
{
struct Node* child;
// First initialize whether the child Node to be deleted has left child.
if (current->leftThread == false)
child = current->left;
// or a right child
else
child = current->right;
// If root node has to be deleted
if (parent == NULL)
root = child;
// If the node to be deleted is left child of its parent
else if (current == parent ->left)
parent ->left = child;
// If the node to be deleted is right child of its parent
else
parent ->right = child;
// Find successor and predecessor
Node* s = inSucc(current);
Node* p = inPred(current);
// If current node has left subtree
if (current->leftThread == false)
p->right = s;
// If current node has right subtree.
else {
if (current->rightThread == false)
s->left = p;
}
// Now memory is freed and new root is returned
free(current);
return root;
}
Case 3: When the node to be deleted has two children
We find the in-order successor of the current Node (Node to be deleted) and then copy the information of this successor into the current Node. After this, the in-order successor Node is deleted using either Case 1 or Case 2.
Let’s have a look at the code:
// Here, 'parent ' is a pointer referring to the parent node
// and 'current' is a pointer to the current node
struct Node* case3(struct Node* root, struct Node* parent, struct Node* current)
{
// Find the inorder successor
struct Node* parsucc = current;
struct Node* succ = current->right;
// Find the leftmost child
while (succ->leftThread==false) {
parsucc = succ;
succ = succ->left;
}
current->data = succ->data;
if (succ->leftThread == true && succ->rightThread == true)
root = case1(root, parsucc, succ);
else
root = case2(root, parsucc, succ);
return root;
}