Threaded Binary Tree

The linked form of binary trees wastes storage capacity because more than half of the connection variables have a Missing value.

A binary tree has several nodes. Hence n+1 link fields have NULL values. Perlis & Thornton came up with a solution where special links spun into yarn are used in place of NULL links to implement the capacity better.

These threaded binary trees were referred to as binary trees having threads. A threaded binary tree has nodes linked to certain other nodes in the tree or threaded to certain other tree nodes.

Threaded Binary Trees are categorized into Two types:

One-way Threaded Binary Tree
Two-way Threaded Binary Tree

One-way Threaded Binary Tree

A thread may start showing up in either the right or left link attribute of a node inside one thread tree. This should link to the following node, which will show after executing an order traverse if it exists in the right link field of a graph. Right-threaded binary trees are these species of trees.

A thread will link to the node's precursor if it occurs in the left field of the component. Left threaded binary trees are these types of trees.

Given that they lack the final benefits of right-threaded binary trees, left-thread binary trees are utilized less frequently. The rights link field from the last node and the left connection field of the first node inside one threaded tree carries a NULL.

The inorder traverse with this binary tree results in D, B, E, A, C, and F, as seen in the above image.

Whenever this tree was displayed as a right-threaded binary tree, node B, which would be the in-order successors of leaf node D, is pointed to instead of the right link element of leaf node D, which also currently has a NULL value. Similar to how NULL value would appear in these other nodes with values inside the right link element.

Two-Way Threaded Binary Tree

In two-way threaded Binary trees, the left area of such a node having NULL values is changed by a thread which refers to a node in order predecessors, and the right link field of either a node having a Default value is substituted by a thread that refers to a node in order successors.

The in-order traversal of this binary tree results in D, B, E, G, A, C, and F, as shown in the above image.

When using a two-way threaded binary tree, threads connecting to node B's in-order predecessor, node E, replace the node's left field when it contains NULL. Similarly, threads are being used to modify node G's right and left linked values so that the right link area points to the datatype in order successor and the left linked field refers to the node's in order precedent. Similarly, threads are added to those other nodes with link variables with Empty values.

We found that neither left thread is available for the first node and also, no right thread is feasible for the last node in the two-way threading binary tree in the mentioned figure. This is due to the absence of their corresponding ordered list antecedent and sequel.

Thread going somewhere serve as a clue to this. So, we keep special expresses the principle of the head node to ensure the consistency of the threads. The left connection field of the header node links to the tree's root, and the right link value points toward the header node itself. A head node also does not include data parts. This header node is becoming the inorder precursor of the first element and the inorder successor throughout the last node if it should be in the 2 threaded binary tree.

Threaded Binary Tree Advantages:

Threaded Binary Tree enables the linear traversal of the elements.
As the threaded binary tree follows linear traversal, usage of stack is eliminated.
We can easily find the parent node without using any parent pointer.
In the inorder fashion, the threaded binary tree gives the forward and backward traversals.
The nodes in the threaded binary tree consists of the pointers for the inorder predecessor and the inorder successor.
One of the predominant advantages of threaded binary tree is that, the optimal usage of the memory.

Let’s look at the implementation of Inorder traversal for the Threaded Binary Tree.

Algorithm for Threaded Binary Tree Inorder Traversal.

Algorithm InorderTraversal(I)  

{  

  ThreadedTreeNode *Header;  

  Header=I;  

  While (1)  

  {  

    I=FindInorder_Successor(H);  

    if (I == Header)  

     return;  

    else  

     print (I->info);  

   }  

}

The above algorithm depicts the inorder traversal for threaded binary trees.

Threaded Binary Tree pseudocode in C Language:

\
#include <stdio.h>  
#include <stdlib.h>  
typedef enum {false, true} boolean;  
struct node *inorder_succ (struct node *p);  
struct node *inorder_pred (struct node *p);  
struct node *insert (struct node *root, int insrtkey);  
struct node *del (struct node *root, int dltekey);  
struct node *case_a (struct node *root, struct node *pa, struct node *pt);  
struct node *case_b (struct node *root,struct node *pa, struct node *pt);  
struct node *case_c (struct node *root, struct node *pa, struct node *pt);  
void inorder_traversal (struct node *root);  
void preorder_traversal (struct node *root);  
  
struct node  
{  
        struct node *left;  
        boolean leftthread;  
        int info;  
        boolean rightthread;  
        struct node *right;  
};  
int main ( )  
{  
 
    int option, number;  
        struct node *root = NULL;  
        while (1)  
        {  
           printf ("\n Threaded Tree Program in C Language: \n");  
                printf (" 1. Insert \n");  
                printf (" 2. Delete \n");  
                printf (" 3. Inorder Traversal \n");  
                printf (" 4. Preorder Traversal \n");  
                printf (" 5. Quit \n");  
                printf (" \n Choose an Option from the above List: \n ");  
                scanf (" %d ", &option);  
                switch (option)  
                {  
                 case 1:  
                        printf ("\n Give the number which is to be inserted in to the Binary Tree: \n ");  
                        scanf (" %d ", &number);  
                        root = insert (root, number);  
                        break;  
                 case 2:  
                        printf ("\n Give the number value which is to be deleted: \n ");  
                        scanf (" %d ", &number);  
                        root = del (root, number);  
                        break;  
                 case 3:  
                        inorder_traversal (root);  
                        break;  
                 case 4:  
                        preorder_traversal (root);  
                        break;  
                 case 5:  
                         exit (1);  
  
                 default:  
                        printf ("\n Option provided is wrong! \n");  
        }  
    }  
        return 0;  
}  
struct node *insert (struct node *root, int insrtkey)  
{  
    struct node *temp, *pa, *pt;  
    int flag = 0;  
    pt = root;  
    pa = NULL;  
    while (pt != NULL)  
    {  
        if (insrtkey == pt -> info)  
        {  
            flag = 1;  
            break;  
        }  
        pa = pt;  
        if (insrtkey < pt -> info)  
        {  
            if (pt -> leftthread == false)  
                pt = pt -> left;  
            else  
                break;  
        }  
        else  
        {  
          	 if (pt -> rightthread == false)  
          	      	pt = pt -> right;  
          	  else  
      	          break;  
        }  
   }  
 if(flag)  
        printf ("\n It is a Duplicate key. \n ");  
    else  
    {  
        temp = (struct node *) malloc (sizeof (struct node));  
        temp -> info = insrtkey;  
        temp -> leftthread = true;  
        temp -> rightthread = true;  
        if (pa == NULL)  
        {  
            root=temp;  
            temp -> left = NULL;  
            temp -> right = NULL;  
        }  
        else if (insrtkey < pa -> info )  
        {  
            temp -> left = pa -> left;  
            temp -> right = pa;  
            pa -> leftthread = false;  
            pa -> left = temp;  
        }  
        else  
        {  
            temp -> left = pa;  
            temp -> right = pa -> right;  
            pa -> rightthread = false;  
            pa -> right = temp;  
        }  
    }  
    return root;  
}  
  
struct node *del (struct node *root, int dltekey)  
{  
    struct node *pa,*pt;  
    int flag=0;  
    pt = root;  
    pa = NULL;  
    while (pt != NULL)  
    {  
        if (dltekey == pt -> info)  
	   {		
            flag =1;  
            break;  
        }  
        pa = pt;  
        if (dltekey < pt -> info)  
        {  
            if (pt -> leftthread == false)  
                pt = pt->left;  
            else  
                break;  
        }  
        else  
        {  
            if (pt -> rightthread == false)  
                pt = pt -> right;  
            else  
                break;  
        }  
    }  
    if (flag == 0)  
        printf ("\n The given key is not present in the tree. \n");  
    else if (pt -> leftthread == false && pt -> rightthread == false)
/*
2 children
*/  
        root = case_c (root, pa, pt);  
    else if (pt -> leftthread == false)  
    root = case_b (root, pa, pt);  
    else if (pt -> rightthread == false)  
    root = case_b (root, pa, pt);  
    else  
        root = case_a (root, pa, pt);  
    return root;  
}  
  
struct node *case_a (struct node *root, struct node *pa, struct node *pt)  
{  
    if (pa == NULL)  
        root = NULL;  
    else if (pt == pa -> left)  
    {  
        pa -> leftthread = true;  
        pa -> left = pt -> left;  
    }  
    else  
    {  
        pa -> rightthread = true;  
        pa -> right = pt -> right;  
    }  
    free (pt);  
    return root;  
}  
struct node *case_b (struct node *root, struct node *pa, struct node *pt)  
{  
    struct node *child, *succ, *pre;  
    if (pt -> leftthread == false)  
        child = pt -> left;  
    else  
        child = pt -> right;  
        if (pa == NULL)     
                root = child;  
        else if (pt == pa -> left)   
                pa -> left = child;  
        else                       
                pa -> right = child;  
        succ = inorder_succ (pt);  
        pre = inorder_pred (pt);  
        if (pt -> leftthread == false)   
                        pt -> right = succ;  
        else  
        {  
        if (pt -> rightthread == false)   
                        succ -> left = pre;  
        }  
        free (pt);  
        return root;  
}   
struct node *case_c (struct node *root, struct node *pa, struct node *pt)  
{  
        struct node *suc, *parsuc;  
        parsuc = pt;  
        suc = pt -> right;  
        while (suc -> left != NULL)  
        {  
                parsuc = suc;  
                suc = suc -> left;  
        }  
        pt -> info = suc -> info;  
        if (suc -> leftthread == true && suc -> rightthread == true)  
                root = case_a (root, parsuc, suc);  
        else  
                root = case_b (root, parsuc, suc);  
        return root;  
}  
struct node *inorder_succ (struct node *pt)  
{  
        if (pt -> rightthread == true)  
                return pt -> right;  
        else  
        {  
                pt = pt -> right;  
                while (pt -> leftthread == false)  
                        pt = pt -> left;  
                return pt;  
        }  
}   
struct node *inorder_pred (struct node *pt)  
{  
        if (pt -> leftthread == true)  
                return pt -> left;  
        else  
        {  
                pt = pt -> left;  
                while (pt -> rightthread == false)  
                        pt = pt -> right;  
                        return pt;  
        }  
}  
void inorder_traversal (struct node *root)  
{  
        struct node *pt;  
        if (root == NULL)  
        {  
                printf ("The given tree is empty. \n");  
                return;  
        }  
        pt = root;  
        while (pt -> leftthread == false)  
                pt = pt -> left;  
        while (pt != NULL )  
        {  
                printf (" %d ", pt -> info);  
                pt = inorder_succ (pt);  
        }  
}  
void preorder_traversal (struct node *root)  
{  
        struct node *pt;  
        if (root == NULL)  
        {  
                printf (" Tree is empty \n ");  
                return;  
        }  
        pt=root;  
        while (pt != NULL)  
        {  
                printf (" %d ", pt -> info);  
                if (pt -> leftthread == false)  
                        pt = pt -> left;  
                else if (pt -> rightthread == false)  
                        pt = pt -> right;  
                else  
                {  
                        while (pt != NULL && pt -> rightthread == true)  
                                pt = pt -> right;  
                        if (pt != NULL)  
                                pt = pt -> right;  
                }  
        }  
}

OUTPUT:

Threaded Tree Program in C Language:

Insert
Delete
Inorder Traversal
Preorder Traversal
Quit