Create Threaded Binary Tree

Lets see how can we create a right threaded binary tree using a recursive function.If current key is inserted as left child of parent,right thread of this key points to its parent and parent’s left link points to this key.If current key is inserted as right child of parent,and if the parent has right thread then right thread of current key is made to point to where right thread of its parent is pointing.Parent’s right link points to this key.

Structure of node for right threaded binary tree (RTBT)

typedef struct node
{
    int key,is_rchild;
    struct node* left,*right;
}

It is similar to structure of node for a binary tree except here we have one additional member field is_rchild.

Value = 1 if a node has right child

Value = 0 if a node has right thread i.e right pointer of the node points to inorder successor.

• Important point

Consider the right threaded binary tree below

eg.

Inorder traversal (left,root,right) of this tree is 10 4 6 8 9

Note : 9 is last node in inorder traversal (no inorder successor).
So it doesn’t have a right thread.

Algorithm to create a RTBT

a)If parent of current node has a right thread,make the right pointer of current node point 
  to node where right pointer of its parent is pointing.

b)Make parent's right pointer point to this current node.

c)Make is_rightchild of parent to 1 which signifies that parent is pointing to its right 
  child and not to its inorder successor i.e right thread of parent doesn't exist.


Recursively create the left subtree (Remember to pass 0 i.e left child)

Recursively create right subtree (Remember to pass 1 i.e right child)

Functions used

1.  int main()

Declare root node and assign it to NULL.
Calls create(&root,0). (Note:address of root node is passed so that changes done to root node in create function would be reflected in main function).

2.  node* getnode(int key)

Creates a node with passed key and returns it.

3.  void create(node** parent,int child)

Creates RTBT.

Arguments:

node** parent – Points to parent of current node.

Insert root case :
parent and curr point to the root node.

int child – 0 for insert left child and 1 for insert right child

Code 

int main()
{
        node* root=NULL;
        create(&root,0);
      
        return 0;
}

node* getnode(int key)
{
        node* keynode;
        keynode=(node*)malloc(sizeof(node));
        keynode->key=key;
        keynode->left=keynode->right=NULL;
        return keynode;
}

void create(node** parent,int child)
{

    int key;node* curr;

    scanf("%d",&key);

    if(key==-1)
        return;

    if(*parent!=NULL)
    {
        curr=getnode(key);

        if(child==0)                                 //left child
        {
            curr->right=*parent;
            (*(*parent)).left=curr;
        }
        else                                         //right child
        {
            if((*(*parent)).right!=NULL)            //if parent has a right thread
                curr->right=(*(*parent)).right;

            (*(*parent)).right=curr;
            (*(*parent)).is_rchild=1;
        }
    }

    else
    {
        curr=getnode(key);
        *parent=curr;
    }

    //Take left child of key

    printf("Enter left child of %d ",curr->key);
    create(&curr,0);                              //0 = left child

    //Take right child of key

    printf("Enter right child of %d ",curr->key);
    create(&curr,1);                              //1 = right child    
}

Code tracing