What is a threaded binary tree?

struct node
{
int value;
struct node *left;
struct node *right;
int rthread;
}

Function to find the inorder successor

mynode *inorder_successor(mynode *x)
{
mynode *temp;

temp = x->right;

if(x->rthread==1)return(temp);

while(temp->left!=NULL)temp = temp->left;

return(temp);
}

Function to traverse the threaded tree in inorder

void inorder(mynode *head)
{
mynode *temp;

if(head->left==head)
{
printf("\nTree is empty!\n");
return;
}

temp = head;

for(;;)
{
temp = inorder_successor(temp);
if(temp==head)return;
printf("%d ", temp->value);
}

}

Inserting toward the left of a node in a threaded binary tree.

void insert(int item, mynode *x)
{
mynode *temp;
temp = getnode();
temp->value = item;
x->left = temp;
temp->left=NULL;
temp->right=x;
temp->rthread=1;
}

Function to insert towards the right of a node in a threaded binary tree.

void insert_right(int item, mynode *x)
{
mynode *temp, r;

temp=getnode();
temp->info=item;
r=x->right;
x->right=temp;
x->rthread=0;
temp->left=NULL;
temp->right=r;
temp->rthread=1;
}

Function to find the inorder predecessor (for a left threaded binary three)

mynode *inorder_predecessor(mynode *x)
{
mynode *temp;

temp = x->left;

if(x->lthread==1)return(temp);

while(temp->right!=NULL)
temp=temp->right;

return(temp);
}