Deletion in Threaded Binary Search Tree

Posted by Coding Ninjas
Deletion in Threaded Binary Search Tree
Deletion in Threaded Binary Search Tree

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.

binary_search_tree

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

binary_search_tree2

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.

binary_search_tree3

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

binary_search_tree4

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;
}

Complete Code for Deletion

#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    struct Node *left, *right;
    int data;
 
    // false if the left pointer points to a predecessor of in Inorder Traversal
    bool leftThread;
 
    // false if the right pointer points to a predecessor of in Inorder Traversal
    bool rightThread;
};
 
// For inserting a Node in Threaded Binary Tree
struct Node* insert(struct Node* root, int key)
{
    // Searching for a Node with given value
    Node* current = root;
    Node* parent = NULL; 

    while (current != NULL) {

        // If value already exists, then we will return the root
        if (key == (current->data)) {
            printf("Duplicate value !\n");
            return root;
        }
 
        // Updating the parent pointer
        parent = current;  

        // Taking the left subtree
        if (key < current->data) {
            if (current->leftThread == false)
                current = current->left;
            else
                break;
        }
 
        // Taking the right subtree
        else {
            if (current->rightThread == false)
                current = current->right;
            else
                break;
        }
    }
 
    // Creating a new Node
    Node* temp = new Node;
    temp->data = key;
    temp->leftThread = true;
    temp->rightThread = true;
 
    if (parent == NULL) {
        root = temp;
        temp->left = NULL;
        temp->right = NULL;
    }

    else if (key < (parent->data)) {
        temp->left = parent->left;
        temp->right = parent;
        parent->leftThread = false;
        parent->left = temp;
    }

    else {
        temp->left = parent;
        temp->right = parent->right;
        parent->rightThread = false;
        parent->right = temp;
    }
 
    return root;
}
 
// For returning the inorder successor using left and right children 
struct Node* inSucc(struct Node* current)
{
    if (current->rightThread == true)
        return current->right;
 
    current = current->right;
    while (current->leftThread == false)
        current = current->left;
 
    return current;
}
 
// For returning inorder successor using rightThread 
struct Node* inorderSuccessor(struct Node* current)
{
    // If rightThread is set, we can quickly find
    if (current->rightThread == true)
        return current->right;
 
    // Or return the leftmost child of right subtree
    current = current->right;
    while (current->leftThread == false)
        current = current->left;
    return current;
}
 
// Print the threaded tree
void inorder(struct Node* root)
{
    if (root == NULL)
        printf("Tree is empty");
 
    // Taking leftmost Node
    struct Node* current = root;
    while (current->leftThread == false)
        current = current->left;
 
    while (current != NULL) {
        printf("%d ", current->data);
        current = inorderSuccessor(current);
    }
}
 
struct Node* inPred(struct Node* current)
{
    if (current->leftThread == true)
        return current->left;
 
    current = current->left;
    while (current->rightThread == false)
        current = current->right;
    return current;
}
 
// 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;
}
 
// 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;
}
 
// 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;
}

 
// 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)
{
    // For initializing the parent node as NULL and current node as root.
    struct Node *parent  = NULL, *current = root;
 
    // Set true if value is found
    int found = 0;
 
    // Searching 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 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;
}

// Driver Program
int main()
{
    struct Node* root = NULL;
 
    root = insert(root, 45);
    root = insert(root, 8);
    root = insert(root, 24);
    root = insert(root, 20);
    root = insert(root, 15);
    root = insert(root, 30);
    root = insert(root, 23);
    root = insert(root, 18);
 
    root = dThreadedBST(root, 24);
    inorder(root);
 
    return 0;
}

Output

8 15 18 20 23 30 45

Time complexity – O(h), where h is the height of the threaded binary search tree. The height of the tree can be ‘n’ in the worst case, and all the keys are deleted in ascending or descending order (Skewed Tree) where all the nodes except the leaf have only one child, and we may have to travel from root to the deepest leaf node.

Space complexity – O(1), as we are not using any additional auxiliary space.

Frequently Asked Questions 

What is a Threaded Binary SearchTree?

A threaded binary search tree is a variation of a normal binary search tree. In a threaded binary search tree, if the left pointer of a node is NULL, it is pointed to its in-order predecessor (if it exists), and if the right pointer of a node is NULL, it is pointed to its in-order successor (if it exists) using links called as threads.

How do you perform deletion in a Threaded Binary search tree?

Yes, we can perform deletion in a threaded binary search tree like it is performed in a binary search tree. First, we will search the value to be deleted and then see the possible cases for deleting it. There are mainly three cases when performing deletion:
1. When a leaf node is to be deleted.
2. When the node to be deleted has only one child.
3. When the node to be deleted has two children.

What are the advantages of a Threaded Binary Tree?

Some advantages of a Threaded Binary tree are:
1. They do not require a stack or recursion for their traversal.
2. In threaded binary trees, memory is not wasted as whenever a node’s left/right pointer is NULL, its inorder predecessor/successor is stored.
3. We can do a backward traversal in a double-threaded binary tree.
4. In-order traversal is fast in a threaded binary tree than a normal binary tree.

Key Takeaways

In this article, we learned about ways to delete a node in threaded binary search trees. Majorly three prominent cases arrive when we try to delete a node. The first one is when the node is a leaf node, the second one when the node to be deleted has only one child (that means left or right pointer is not NULL), and the third one is when the node has two children (that means both left and right child pointers are not NULL). Hence, we traversed the tree, keeping in mind all three cases.

By: Mehak Goel 

Tags:
Coding Ninjas Logo

CODING NINJAS

About Us

Privacy Policy

Terms & Condition

Pricing & Refund Policy

Bug Bounty

Customers

Press Release

PRODUCTS

Courses

Career Camp

Captain Coder

Hire Talent

COMMUNITY

CodeStudio

Blog

Events

Campus Ninja

Important Links

Coding Courses for Beginners:

C++ Foundation with Data Structures | JAVA Foundation with Data Structures | Interview Preparation Course | Competitive Programming Course | Python Foundation with Data Structures | Aptitude Preparation Course

Advanced Coding Course:

Advanced Front-End Web Development with React | Machine Learning and Deep Learning Course | Full Stack Web Development Course | Data Science & Machine Learning Complete | Android Development with Kotlin

Career Tracks:

Ninja Competitive Programmer Track | Ninja Android Developer Career Track | Ninja Web Developer Career Track - NodeJS & ReactJs | Ninja Web Developer Career Track - NodeJS | Ninja Data Scientist Career Track | Ninja Machine Learning Engineer Career Track

Free Trial:

C++ Foundation with Data Structures | Java Foundation with Data Structures | Competitive Course | Aptitude Preparation Course | Python Foundation with Data Structures | Android Development with Kotlin Language | Full Stack Web Development with NodeJS | Advanced Front-End Web Development with React | Data Science & Machine Learning Complete | Interview Preparation Course | Machine Learning Course

Free Contents:

C++ Foundation with Data Structures | Java Foundation with Data Structures | Competitive Programming Course | Aptitude Preparation Course | Python Foundation with Data Structures | Android Development with Kotlin Language | Full Stack Web Development with NodeJS | Advanced Front-End Web Development with React | Data Science & Machine Learning Complete | Interview Preparation Course