Right in threaded Binary tree without recursion(Without storing inorder traversal)

A threaded binary tree makes it possible to traverse the values in the binary tree via a linear traversal that is more rapid than a recursivein-order traversal. It is also possible to discover the parent of a node from a threaded binary tree, without explicit use of parent pointers or a stack, albeit slowly. This can be useful where stack space is limited, or where a stack of parent pointers is unavailable (for finding the parent pointer via DFS).

A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (ifit exists) .


C code::

#include<stdio.h>
struct node//defining node of tree
{
int data;
struct node *l,*r,*rth;
int rthread;
};
typedef struct node node;
getnode()
{
return ((node *)malloc(sizeof(node)));
}
insert(int val,node *root)//function to insert node after root
{
node *p=getnode();
p->data=val;
p->l=NULL;
p->r=NULL;
p->rthread=1;
p->rth=NULL;
if(val<root->data&&root->l!=NULL)
{
return insert(val,root->l);
}
if(val>=root->data&&root->r!=NULL)
{
return insert(val,root->r);
}
if(val>=root->data&&root->r==NULL)
{
root->r=p;
root->rthread=0;
return;
}
if(val<root->data&&root->l==NULL)
{
root->l=p;
return;
}
}
int i=0;
leftmost(node *n)//function to go to leftmost node of the given node
{
    if(n==NULL){return NULL;}
    while(n->l!=NULL)
        n=n->l;
    return n;
}
int la=0;
search(node *root,int key)//function to search node
{
if(root->data==key){return root;}
if(root->data<key){return search(root->r,key);}
if(root->data>key){return search(root->l,key);}
}
parent(node *root,int v)//function to get parent of a node
{
    if(root->data==v){return root;}
    if(root->data>v){if(root->l->data==v){return root;}else return parent(root->l,v);}
    if(root->data<v){if(root->r->data==v){return root;}else return parent(root->r,v);}
}
main()
{
int k;
printf("Enter the total number of nodes you want to enter");
scanf("%d",&k);
int a[k];
int ir;
for(ir=0;ir<k;ir++)
{
    printf("\nEnter %d element",ir+1);
    scanf("%d",&a[ir]);
}
node *root=getnode();
root->data=a[0];
root->l=NULL;
root->r=NULL;
root->rthread=1;
root->rth=NULL;
node *p=root;
for(ir=1;ir<k;ir++)
{
insert(a[ir],root);
root=p;
}
root=p;
for(ir=0;ir<k;ir++)//For threading
{
    node *child=search(root,a[ir]);

    if(child->rthread==1)
    {
       node *par=parent(root,a[ir]);
       root=p;
       if(par->l==child){child->rth=par;continue;}
       if(par->r==child){
            node *ip=parent(root,par->data);
        while(ip->l!=par)
        {
            root=p;
        par=ip;
            ip=parent(root,par->data);
            root=p;
        if(ip->data==a[0]&&ip->l!=par){break;}
        }
        if(ip->l==par){child->rth=ip;}

       }

    }
root=p;
}
printf("Inorder using rthread without recursion\n");
root=p;
node *cur=leftmost(root);
while(cur!=NULL)
{
    printf("%d\n",cur->data);
    if(cur->rth!=NULL)
    {
        cur=cur->rth;
    }
    else
    {
        cur=leftmost(cur->r);
    }
}
}