Part II: Threaded Binary Search Tree Traversal

Inorder

Algorithm:
Follow the tree towards the left, print the smallest value and then move on to print the next smallest value so that finally we will be printing all the value in the ascending order. This one can be achieved simply by using recursive algorithm as follows:
For the general binary search tree,
void inorder(struct node *tree)
{
    if(tree==NULL)
        return;
    inorder(tree->left);
    printf(" %d ",tree->info);
    inorder(tree->right);
}

However, the inorder code for Threaded binary search tree isnot as simple, the code is given below

struct node *inorder_successor(struct node *tree)
{
    struct node *temp;
    temp=tree->right;
    if(tree->isright==0) //here we are checking if the tree is a leaf ( not the temp)
        return temp;
    while(temp->isleft==1)
        temp=temp->left;
    return temp;
}
/*Thus, what we are doing in the above steps are first checking if the tree is a leaf. If so we are returning temp (which is right of the tree), otherwise we are going to find the inorder successor of that tree. */
void inorder(struct node *head_tree)
{
    struct node *tree;
    printf("\n\n");
    tree=head_tree->left;
    if(tree==NULL)
    {
        printf("\nNo element in the tree.");
        return;
    }
    while(tree->left!=head_tree)
        tree=tree->left;
    do
    {
        printf(" %d ",tree->info);
        tree=inorder_successor(tree);
        if(tree==head_tree)
            break;
    }while(1);
    printf("\n\n");
}

We are using two functions here, one for the traversal and one to find the inorder succesor after traversing any node. By the way, the traversal has started from the first inorder element. (not the root of the tree)

Preorder

In preorder, for any node we first print the value of the node and then follow its left and after printing all its left value we follow the right and print all the value.
For general binary search tree, the recursive algorithm is as follows:
void preorder(struct node *tree)
{
    if(tree==NULL)
          return;
    printf(" %d ",tree->info);
    preorder(tree->left);
    preorder(tree->right);
}
However, we do it in the similar fashion as inorder for the threaded binary trees by using two functions respectively to traverse and find the preorder successor. The code for the preorder traversal is given below:

struct node *preorder_successor(struct node *tree,struct node *head_tree)
{
    struct node *temp;
    if(tree->isleft==1)
        return tree->left;
    if(tree->isright==1)
        return tree=tree->right;
    while(tree->isright==0)
    {
        tree=tree->right;
        if(tree==head_tree)
            return head_tree;
    }
    return tree->right;
}
void preorder(struct node *head_tree)
{
    struct node *tree;
    tree=head_tree->left;
    printf("\n\n");
    if(tree==NULL)
    {
        printf("\nNo element in the tree.\n");
        return;
    }
    do
    {
        printf("  %d  ",tree->info);
        tree=preorder_successor(tree,head_tree);
        if(tree==head_tree)
            return;
    }while(1);
    printf("\n\n");
}

Postorder 

In the postorder successor, for any node we follow the left link and print all the values and then follow the right one and print all the values and finally print the value of that node.
For the general binary search tree, the postorder code is below
void postorder(struct node *tree)
{
    if(tree==NULL)
          return;
    postorder(tree->left);
    postorder(tree->right);
    printf(" %d ",tree->info);
}
However, for the threaded binary search tree, it is the trickiest. Following algorithm I used to write a code from the following address http://stackoverflow.com/questions/10694037/postorder-traversal-of-tree-without-using-recursion-or-stack

The algorithm goes as follows 

• A variable can be used to check type of current action.
• If action is left traversal and current node has a left descendant, then descendant is traversed. Otherwise action changed to right traversal.
• If action is right traversal and current node has a left descendant, action changed to left traversal. Otherwise action changed to visiting a node.
• If action is visiting node: current node is visited, afterwards its postorder successor has to be found.
• If current node’s parent accessible through a thread (i.e. current node is parent’s left child) then traversal is set to continue with the right descendant of parent.
• If current node has no right descendant, this is the end of the right-extended chain of nodes.
• First: the beginning of the chain is reached through the thread of the current node.
• Second: right references of nodes in the chain is reversed.
• Finally: chain is scanned backward, each node is visited, then right references are restored to previous settings.

 The code goes as follow
enum my_enum {LEFT_TRAVERSAL=0,RIGHT_TRAVERSAL,CURRENT_VISITING};
void chain_formation(struct node *tree)
{
    struct node *start_chain,*parent,*temp;
    parent=tree;
    start_chain=tree->left;
    if(start_chain->right==tree)
        printf("  %d  ",start_chain->info);
    while(start_chain->right!=tree)
    {
        temp=start_chain->right;
        start_chain->right=parent;
        parent=start_chain;
        start_chain=temp;
    }
    while(start_chain!=tree)
    {
        printf(" %d ",start_chain->info);
        temp=parent->right;
        start_chain=parent;
        parent=temp;
    }
      
}
void postorder(struct node *head_tree)
{
    enum my_enum traversal;
    struct node *tree,*parent;  
    tree=head_tree->left;
    printf("\n\n");
    traversal=LEFT_TRAVERSAL;
    int i=20;
    do
    {
        switch(traversal)
        {
            case LEFT_TRAVERSAL:
                        parent=tree;
                        while(tree->isleft!=0)
                        {
                            parent=tree;
                            tree=tree->left;
                        }
                        traversal=RIGHT_TRAVERSAL;
                        break;
            case RIGHT_TRAVERSAL:
                        if(tree->isright==0)
                        {
                            traversal=CURRENT_VISITING;
                            break;
                        }
                        parent=tree;
                        tree=tree->right;
                        if(tree->isleft==1)
                            traversal=LEFT_TRAVERSAL;
                        else if(tree->isright==1)
                            traversal=RIGHT_TRAVERSAL;
                        else
                            traversal=CURRENT_VISITING;
                        break;
            case CURRENT_VISITING:                  
                        if(parent->info>tree->info)
                        {
                            printf("  %d  ",tree->info);
                            tree=tree->right;
                            if(parent->isright==0)
                            {
                                parent=parent->right;
                                traversal=CURRENT_VISITING;
                            }
                            else
                                traversal=RIGHT_TRAVERSAL;
                        }
                        else
                        {
                            chain_formation(tree->right);
                            tree=tree->right;
                            if(tree->isright==0)
                                parent=tree->right;
                            traversal=RIGHT_TRAVERSAL;
                        }
                        break;
            default:
                        printf("\nWrong Input\n");
                        break;
      
        }
    }while(tree!=head_tree);
    printf("\n\n");
}