Logo
×

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.

Threaded Binary Tree

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.

Threaded Binary Tree

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

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:

  1. Insert
  2. Delete
  3. Inorder Traversal
  4. Preorder Traversal
  5. Quit

Choose an Option from the above List:

1

Give the number which is to be inserted in to the Binary Tree: 20

Threaded Tree Program in C Language:

  1. Insert
  2. Delete
  3. Inorder Traversal
  4. Preorder Traversal
  5. Quit

Choose an Option from the above List:

1

Give the number which is to be inserted in to the Binary Tree: 30

Threaded Tree Program in C Language:

  1. Insert
  2. Delete
  3. Inorder Traversal
  4. Preorder Traversal
  5. Quit

Choose an Option from the above List:

1

Give the number which is to be inserted in to the Binary Tree: 40

Threaded Tree Program in C Language:

  1. Insert
  2. Delete
  3. Inorder Traversal
  4. Preorder Traversal
  5. Quit

Choose an Option from the above List:

1

Give the number which is to be inserted in to the Binary Tree: 10

Threaded Tree Program in C Language:

  1. Insert
  2. Delete
  3. Inorder Traversal
  4. Preorder Traversal
  5. Quit

Choose an Option from the above List:

Give the number which is to be inserted in to the Binary Tree: 25

Threaded Tree Program in C Language:

  1. Insert
  2. Delete
  3. Inorder Traversal
  4. Preorder Traversal
  5. Quit

Choose an Option from the above List:

2

Give the number value which is to be deleted: 25

Threaded Tree Program in C Language:

  1. Insert
  2. Delete
  3. Inorder Traversal
  4. Preorder Traversal
  5. Quit

Choose an Option from the above List:

2

Give the number value which is to be deleted: 28

The given key is not present in the tree.

Threaded Tree Program in C Language:

  1. Insert
  2. Delete
  3. Inorder Traversal
  4. Preorder Traversal
  5. Quit

Choose an Option from the above List:

3

10 20 30 40

Threaded Tree Program in C Language:

  1. Insert
  2. Delete
  3. Inorder Traversal
  4. Preorder Traversal
  5. Quit

Choose an Option from the above List:

4

20 10 30 40

Threaded Tree Program in C Language:

  1. Insert
  2. Delete
  3. Inorder Traversal
  4. Preorder Traversal
  5. Quit

Choose an Option from the above List:

5

Related Topics

String Operations in Data Structures

Operations on Strings Reversing the order of words in a sentence Reversing a string is a technique that reverses or alters the order of a given string so that the last character...

9 minutes read.

Does Overloading Work with Inheritance

This is a question that occasionally comes to many programmers. Who are curious to know more now has a complete explanation and a solution through this tutorial! Inheritance: The functions of...

3 minutes read.

Convert binary tree to a doubly linked list

Implementation //creating a C++ program for the transition of a binary tree into a linked list. #include <iostream> using namespace std; /* Firstly, let’s create a binary tree that will help us in setting...

4 minutes read.

Array vs Linked List: Data Structure

Data structure: Difference Between Array and Linked List What is Array? An array is a linear data structure that can store similar data items for further processing. The similar data items...

3 minutes read.

Operations on 1D-Arrays

One Dimensional Array Operations Basic Methods The fundamental operations enabled by an array are listed below. Traverse prints each element of the array one by one.Insert a new element at the specified index.Delete...

8 minutes read.

Stack Using Linked List

In the linked list implementation of the stack, we use a linked list as the primitive data structure to create the stack. It is called the dynamic implementation of the...

6 minutes read.

Red Black Tree

Red Black Tree A red-black tree is referred as self-balancing binary search tree. The tree was invented by Rudolf Bayer in 1972. In red-black, each node stores an extra bit that...

8 minutes read.

Given a Binary Tree, Print the Pre-order Traversal in Recursive

Implementation #include <stdio.h> #include <stdlib.h>   /* Creating a binary tree node that consists of some data along with the pointer to the left and right child.  */ struct __nod {     int record;     struct...

4 minutes read.

Merge two sorted linked lists

Merge two sorted linked lists In this article, we are going to learn how to merge two linked lists. Here we have given two linked lists that are sorted in increasing...

7 minutes read.

Invert binary tree

Invert binary tree is a mirror image of a tree. It is pretty much the same compared to the only difference: its left and right children are swapped with the...

4 minutes read.

Deletion in Binary Search Tree

Implementation #include <iostream> using namespace std; struct _nod {   int ky;   struct _nod *Lft, *Rt; }; // Creating a node in the binary tree. struct _nod *nw_nod(int Itm) {   struct _nod *temp = (struct _nod *)malloc(sizeof(struct...

4 minutes read.

Data Structures Algorithms

What is an Algorithm? An algorithm is a sequence of steps used to complete a job or get a desired result. It is similar to programming building elements that let cell...

4 minutes read.

Horizontal and Vertical Scaling

Being a software engineer, you would have designed a website or application and deployed it on any server. Imagine that the developed application starts getting popular, and many users engage...

6 minutes read.

What is a full Binary Tree?

A full binary tree is considered to be a special kind of binary tree in which every single node or leaf node present either contains two children or no children...

4 minutes read.

Linear Queue Data Structure in C

Data Structure There are many ways to store data in programming, that Queue has features that make it all the more special. We all know that data structure is a way...

9 minutes read.

Convert Sorted List to Binary Search Tree

Implementation // creating the C++ implementation of the following approach: - #include <bits/stdc++.h> using namespace std; /* Create the link list node and see its implementation. */ class L__Nod { public: int record; L__Nod* next; }; /* constructing a new binary...

15 minutes read.

LCA of binary tree

Implementation //Writing a program to find the lowest common factor in a given binary search tree. #include <iostream> #include <vector> using namespace std; // the very first step is to create a binary tree. struct __nod { int...

8 minutes read.

Create a binary search tree

Implementation In this section of the article, we will see the usage and mechanism of how we will create a given binary tree. Let's observe these in more depth and then...

7 minutes read.

Buffer overflow attack with examples

You have undoubtedly faced the term buffer overflow in your programming journey. Many times it occurs when we try to run a piece of code with user input, but it...

4 minutes read.

Singly Linked list

Singly Linked list A singly linked list is a kind of linked list which is unidirectional. If we talk about singly linked list, then we can say it can be traversed...

3 minutes read.