Operations in Threaded Binary Tree

Hrithik Shrivastava -

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

There are three main operations which can be done on a threaded binary tree:

  1. Insert
  2. Search
  3. Delete

In these operations I'm using a doubly threaded binary tree let's look at them one by one:

Insert in Threaded Binary Tree

If we want to insert new node in threaded binary tree then we can use insert operation.

To insert any node in threaded binary tree three cases might arise

1.When new node is inserted in a empty tree.
2.When new node is inserted as left child of some node in the tree.
3.When new node is inserted as right child of some node in the tree.

Case 1

when new node is inserted in a empty threaded binary search tree we set it's left and right pointers as null pointers , this step is same in both binary as well as threaded binary search tree.

root = tmp;
tmp -> left = NULL;
tmp -> right = NULL;

Case 2

When new node is inserted in binary search tree as left child of some already existing node then node we perform two operations in struct of parent and two operations in struct of child for example -

For Child


for newly inserted child node (temp here ) we set it's left point to left of parent and it's right point to parent.

tmp -> left = par ->left;
tmp -> right = par;

For Parent

For parent of the child node inserted we set it's lthread to true indicating left child exist and also setting it's left as temp cause child node is the new inorder predecessor for the parent node and also it's the left child of the parent.

par -> lthread = true;
par -> left = temp;

Case 3

When new node is inserted as right child of some node we s perform two operations on the child and two operations on parent similar to what we have done in case 2 -

For Child

Let us say the new node inserted is child node and the node to which it's inserted is parent node then we can say that the parent of child inserted is now it's inorder predecessor and the inorder successor of parent is now the inorder succesor for the child node.
So the left and right threads of the new node will be -

// tmp represent child node here

tmp -> left = par;
tmp -> right = par -> right;

For Parent

The right pointer of parent node now points to it's newly inserted node and setting up it's bool variable to true indicating there exists a right child.

// par represents parent node here
par -> rthread = true;
par -> right = tmp;

Code for insertion

// Insert a Node in Binary Threaded Tree
struct Node *insert(struct Node *root, int ikey)
{
    // Searching for a Node with given value
    Node *ptr = root;
    Node *par = NULL; // Parent of key to be inserted
    while (ptr != NULL)
    {
        // If key already exists, return
        if (ikey == (ptr->info))
        {
            printf("Duplicate Key !\n");
            return root;
        }
 
        par = ptr; // Update parent pointer
 
        // Moving on left subtree.
        if (ikey < ptr->info)
        {
            if (ptr -> lthread == false)
                ptr = ptr -> left;
            else
                break;
        }
 
        // Moving on right subtree.
        else
        {
            if (ptr->rthread == false)
                ptr = ptr -> right;
            else
                break;
        }
    }
 
    // Create a new node
    Node *tmp = new Node;
    tmp -> info = ikey;
    tmp -> lthread = true;
    tmp -> rthread = true;
 
    if (par == NULL)
    {
        root = tmp;
        tmp -> left = NULL;
        tmp -> right = NULL;
    }
    else if (ikey < (par -> info))
    {
        tmp -> left = par -> left;
        tmp -> right = par;
        par -> lthread = false;
        par -> left = tmp;
    }
    else
    {
        tmp -> left = par;
        tmp -> right = par -> right;
        par -> rthread = false;
        par -> right = tmp;
    }
 
    return root;
}

Time and space complexity for insertion

Time complexity - O(logn)
space complexiy - O(1)

Search operation in Threaded Binary Tree

Search operation in theaded binary tree is pretty simple we just need to follow a simple algorithm that is shown below

If search key < root then
   Go to left thread
else
   Go to right thread

we need to keep repeating the above algorithm until we find the required node , if we are unable to locate the node and reach null we can return -1 indicating that element doesn't exist in the tree.

Code

struct Node *search( struct Node *root , int key ){

     Node *ptr = root ;

     

     while( ptr != nullptr  ){

         if( ptr->info == key ){
             // indicating that the element is found then
             return ptr ;
         }else if( ptr->info < key ){
             // moving to inorder predecessor of the current node 
             ptr = ptr->right ;
         }else{
             // moving to inorder successor of the current node
            ptr = ptr->left ;
         }

     }

     // if element is not found then we can return nullptr indicating element not 
     // found in the given binary search tree
     return nullptr ;

}

Time complexity for searching

Time complexity - O(logn)

Delete operation in Threaded Binary Tree

If we want to delete some node from the given doubly threaded binary search tree then we can use the delete operation but in the delete operation there can be three cases for a node in a doubly threaded binary tree.

Case 1 leaf node needs to be deleted

if we are deleting any node which is on the leaf then it's parent's left or right thread need to be adjusted so if leaf is left child of the parent node then after deletion left thread of the parent node is made to point to left thread of the child
and parent's leftThread is set to false indicating parent is pointing to some inorder predecessor.

parent -> lthread = true;
parent -> left = ptr -> left;

similarly if we are deleting the right child then parent's right is made to point to right thread of child nd rightThread is set to false.

par -> rthread = true;
par -> right = ptr -> right;

Code for case 1

struct Node* case1(struct Node* root, struct Node* par,
                   struct Node* ptr)
{
    // If Node to be deleted is root
    if (par == NULL)
        root = NULL;
 
    // If Node to be deleted is left
    // of its parent
    else if (ptr == par->left) {
        par->lthread = true;
        par->left = ptr->left;
    }
    else {
        par->rthread = true;
        par->right = ptr->right;
    }
 
    // Free memory and return new root
    free(ptr);
    return root;
}

Case 2 node to be deleted has only 1 child left or right

Before deleting such node first it's inorder predecessor and inorder successor is found out -

 s = inSucc(ptr);
 p = inPred(ptr);

then

If Node to be deleted has left subtree, then after deletion right thread of its inorder predecessor should point to its inorder successor.

p->left = s;

If Node to be deleted has right subtree, then after deletion left thread of its inorder successor should point to its inorder predecessor .

s->left = p ;

Code for case 2

struct Node* case2(struct Node* root, struct Node* par,
                   struct Node* ptr)
{
    struct Node* child;
 
    // Initialize child Node to be deleted has
    // left child.
    if (ptr->lthread == false)
        child = ptr->left;
 
    // Node to be deleted has right child.
    else
        child = ptr->right;
 
    // Node to be deleted is root Node.
    if (par == NULL)
        root = child;
 
    // Node is left child of its parent.
    else if (ptr == par->left)
        par->left = child;
    else
        par->right = child;
 
    // Find successor and predecessor
    Node* s = inSucc(ptr);
    Node* p = inPred(ptr);
 
    // If ptr has left subtree.
    if (ptr->lthread == false)
        p->right = s;
 
    // If ptr has right subtree.
    else {
        if (ptr->rthread == false)
            s->left = p;
    }
 
    free(ptr);
    return root;
}

Case 3 node to be deleted has 2 children

We find inorder successor of Node to be deleted and then we copy the information of this inorder successor into current Node. After this inorder successor Node is deleted using either Case 1 or Case 2 explained above.

// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
struct Node* case3(struct Node* root, struct Node* par,
                   struct Node* ptr)
{
    // Find inorder successor and its parent.
    struct Node* parsucc = ptr;
    struct Node* succ = ptr->right;
 
    // Find leftmost child of successor
    while (succ->left != NULL) {
        parsucc = succ;
        succ = succ->left;
    }
 
    ptr->info = succ->info;
 
    if (succ->lthread == true && succ->rthread == true)
        root = case1(root, parsucc, succ);
    else
        root = case2(root, parsucc, succ);
 
    return root;
}

Time and space complexity for deletion

Time complexity - O(logn)
space complexiy - O(1)

Code For Doubly Threaded Tree including insert,search and delete operations

#include <bits/stdc++.h>
using namespace std;

struct Node {
   struct Node *left, *right;
   int info;

   // True if left pointer points to predecessor
   // in Inorder Traversal
   bool lthread;

   // True if right pointer points to predecessor
   // in Inorder Traversal
   bool rthread;
};

struct Node *search( struct Node *root , int key ){

    Node *ptr = root ;

    while( ptr != nullptr  ){

        if( ptr->info == key ){
            // indicating that the element is found then
            return ptr ;
        }else if( ptr->info < key ){
            // moving to inorder predecessor of the current node 
            ptr = ptr->right ;
        }else{
            // moving to inorder successor of the current node
           ptr = ptr->left ;
        }

    }

    // if element is not found then we can return nullptr indicating element not 
    // found in the given binary search tree
    return nullptr ;

} 

// Insert a Node in Binary Threaded Tree
struct Node* insert(struct Node* root, int ikey)
{
   // Searching for a Node with given value
   Node* ptr = root;
   Node* par = NULL; // Parent of key to be inserted
   while (ptr != NULL) {
       // If key already exists, return
       if (ikey == (ptr->info)) {
           printf("Duplicate Key !\n");
           return root;
       }

       par = ptr; // Update parent pointer

       // Moving on left subtree.
       if (ikey < ptr->info) {
           if (ptr->lthread == false)
               ptr = ptr->left;
           else
               break;
       }

       // Moving on right subtree.
       else {
           if (ptr->rthread == false)
               ptr = ptr->right;
           else
               break;
       }
   }

   // Create a new Node
   Node* tmp = new Node;
   tmp->info = ikey;
   tmp->lthread = true;
   tmp->rthread = true;

   if (par == NULL) {
       root = tmp;
       tmp->left = NULL;
       tmp->right = NULL;
   }
   else if (ikey < (par->info)) {
       tmp->left = par->left;
       tmp->right = par;
       par->lthread = false;
       par->left = tmp;
   }
   else {
       tmp->left = par;
       tmp->right = par->right;
       par->rthread = false;
       par->right = tmp;
   }

   return root;
}

// Returns inorder successor using left
// and right children (Used in deletion)
struct Node* inSucc(struct Node* ptr)
{
   if (ptr->rthread == true)
       return ptr->right;

   ptr = ptr->right;
   while (ptr->lthread == false)
       ptr = ptr->left;

   return ptr;
}

// Returns inorder successor using rthread
// (Used in inorder)
struct Node* inorderSuccessor(struct Node* ptr)
{
   // If rthread is set, we can quickly find
   if (ptr->rthread == true)
       return ptr->right;

   // Else return leftmost child of right subtree
   ptr = ptr->right;
   while (ptr->lthread == false)
       ptr = ptr->left;
   return ptr;
}

// Printing the threaded tree
void inorder(struct Node* root)
{
   if (root == NULL)
       printf("Tree is empty");

   // Reach leftmost Node
   struct Node* ptr = root;
   while (ptr->lthread == false)
       ptr = ptr->left;

   // One by one print successors
   while (ptr != NULL) {
       printf("%d ", ptr->info);
       ptr = inorderSuccessor(ptr);
   }
}

struct Node* inPred(struct Node* ptr)
{
   if (ptr->lthread == true)
       return ptr->left;

   ptr = ptr->left;
   while (ptr->rthread == false)
       ptr = ptr->right;
   return ptr;
}

// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
struct Node* case1(struct Node* root, struct Node* par,
                  struct Node* ptr)
{
   // If Node to be deleted is root
   if (par == NULL)
       root = NULL;

   // If Node to be deleted is left
   // of its parent
   else if (ptr == par->left) {
       par->lthread = true;
       par->left = ptr->left;
   }
   else {
       par->rthread = true;
       par->right = ptr->right;
   }

   // Free memory and return new root
   free(ptr);
   return root;
}

// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
struct Node* case2(struct Node* root, struct Node* par,
                  struct Node* ptr)
{
   struct Node* child;

   // Initialize child Node to be deleted has
   // left child.
   if (ptr->lthread == false)
       child = ptr->left;

   // Node to be deleted has right child.
   else
       child = ptr->right;

   // Node to be deleted is root Node.
   if (par == NULL)
       root = child;

   // Node is left child of its parent.
   else if (ptr == par->left)
       par->left = child;
   else
       par->right = child;

   // Find successor and predecessor
   Node* s = inSucc(ptr);
   Node* p = inPred(ptr);

   // If ptr has left subtree.
   if (ptr->lthread == false)
       p->right = s;

   // If ptr has right subtree.
   else {
       if (ptr->rthread == false)
           s->left = p;
   }

   free(ptr);
   return root;
}

// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
struct Node* case3(struct Node* root, struct Node* par,
                  struct Node* ptr)
{
   // Find inorder successor and its parent.
   struct Node* parsucc = ptr;
   struct Node* succ = ptr->right;

   // Find leftmost child of successor
   while (succ->lthread==false) {
       parsucc = succ;
       succ = succ->left;
   }

   ptr->info = succ->info;

   if (succ->lthread == true && succ->rthread == true)
       root = case1(root, parsucc, succ);
   else
       root = case2(root, parsucc, succ);

   return root;
}

// Deletes a key from threaded BST with given root and
// returns new root of BST.
struct Node* deleteFromThreadedBst(struct Node* root, int target)
{
   // Initialize parent as NULL and
   // Node as root.
   struct Node *par = NULL, *ptr = root;

   // Set true if key is found
   int found = 0;

   // Search key in BST : find Node and its
   // parent.
   while (ptr != NULL) {
       if (target == ptr->info) {
           found = 1;
           break;
       }
       par = ptr;
       if (target < ptr->info) {
           if (ptr->lthread == false)
               ptr = ptr->left;
           else
               break;
       }
       else {
           if (ptr->rthread == false)
               ptr = ptr->right;
           else
               break;
       }
   }

   if (found == 0)
       printf("target not present in tree\n");

   // Two Children
   else if (ptr->lthread == false && ptr->rthread == false)
       root = case3(root, par, ptr);

   // Only Left Child
   else if (ptr->lthread == false)
       root = case2(root, par, ptr);

   // Only Right Child
   else if (ptr->rthread == false)
       root = case2(root, par, ptr);

   // No child
   else
       root = case1(root, par, ptr);

   return root;
}

// Driver Program
int main()
{
   struct Node* root = NULL , *temp = NULL;

   root = insert(root, 1);
   root = insert(root, 3);
   root = insert(root, 5);
   root = insert(root, 7);
   root = insert(root, 12);
   root = insert(root, 2);
   root = insert(root, 10);
   root = insert(root, 6);
   
   temp = search(root , 5) ;

   if( temp ) cout<<"Element with value 5 found\n" ;
   else cout<<"element doesn't exist in the given binary threaded tree\n" ;

   root = deleteFromThreadedBst(root, 6);
   inorder(root);

   return 0;
}

Output:

Element with value 5 found
1 2 3 5 7 10 12

Thank you!

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.