Inorder Traversal of Threaded Binary Tree

Algorithm

Make curr = leftmost of root 

Until current node is not NULL

            a)Print current node.

            b)if current node has right thread,then traverse that thread.

            c)If current node = last node.STOP.

            d)else (right child exists for current node) Find leftmost of current node's 
               right subtree and make it current node.

Code

void inorder(node* root)
{
    node* curr = leftmost(root);

    while(curr!=NULL)
    {
            printf("%d",curr->key);

            if(curr->right!=NULL && curr->is_rchild==0)     //right thread exists
                curr = curr->right;

            else if(curr->right == NULL)                    //last node
                break;

            else                                           //right child exists
                curr=leftmost(curr->right);
    }   
}

node* leftmost(node* keynode)
{
    while(keynode->left!=NULL)
        keynode=keynode->left;

    return keynode;
}







Code Tracing