Threaded Binary Tree and its implementation in C

March 10, 2020

Threaded Binary Trees are those in which the NULL right pointers of all nodes are THREADED to its immediate inorder successor in the Binary Tree. Such pointers or THREADS are also called RIGHT IN threads as they are always threaded to right.

Example Structure of a Threaded Binary Tree

                                      
                      A
                    /   \
                   B     C
                 /  \      \
                D    E      F 
                      \    /  \
                       G   H   I
                      /   /   /
                     J   K    L

Inorder traversal : DBEJGACKHFLI

From the above Threaded Binary Tree, we can see 3 NULL right pointers at G, H. From inorder traversal sequence derived above, see how these right pointer nodes are threaded immediately to their inorder successors? Like G threaded to A and H to F. I is also a right NULL right pointer node but tree ends there.

Such as threaded Binary Tree can be implemented dynamically as follows assuming that father field is not preset.

struct nodetype{
                int info;
                struct nodetype * left;
                struct nodetype * right;
                int rthread; /*is TRUE if right is NULL or a no-NULL thread*/
               };
typedef struct nodetype * NODEPTR;

/*routine for maketree*/
NODEPTR maketree(int x){
              NODEPTR getnode (void); NODEPTR p;
              p = getnode();
              p->info = x;
              p->left = p->right = NULL;
              p->rthread = TRUE;
              return(p);
     }

NODEPTR getnode(void){              
              return((NODEPTR) malloc(size of struct nodetype));
          }

/*routine for setright*/
void setright(NODEPTR p, int x){              
              NODEPTR q;
              if(p == NULL)
                    printf("\nVoid insertion\n");
              if(!p->rthread)
                    printf("\nInvalid insertion\n");
              else{
                    q = getnode();
                    q->info = x;
                    r = p->right;
                    p->right = q;
                    q->right = r; /*Inorder successor of node(q) is the previous inorder successor of node(p)*/
                    q->left = NULL;
                    p->rthread = FALSE;                    
                    q->rthread = TRUE;
               }
              return;
           }

/*routine for setleft*/
void setleft(NODEPTR p, int x){
             NODEPTR q;
              if(p == NULL)
                    printf("\nVoid insertion\n");
              if(p->left != NULL)
                    printf("\nInvalid insertion\n");
              else{
                    q = getnode();
                    q->info = x;                    
                    p->left = q;
                    q->left = NULL;                    
                    q->right = p; /*Inorder successor of node(q) is node(p)*/
                    q->rthread = TRUE;
               }
              return;
           }

You might be interested in below articles –