Trees->Non-recursive traversal using a Threaded Binary Tree

I'll consider the INORDER traversal again. Here, for every node, we'll visit the left sub-tree (if it exists) first (if and only if we haven't visited it earlier); then we visit (i.e print its value, in our case) the node itself and then the right sub-tree (if it exists). If the right sub-tree is not there, we check for the threaded link and make the threaded node the current node in consideration. Please, follow the example given below.

		List of visited nodes:	INORDER:
step-1:	'A' has a left child i.e B, which has not been visited. So, we put B in our "list of visited nodes" and B becomes our current node in consideration.	B
step-2:	'B' also has a left child, 'D', which is not there in our list of visited nodes. So, we put 'D' in that list and make it our current node in consideration.	B D
step-3:	'D' has no left child, so we print 'D'. Then we check for its right child. 'D' has no right child and thus we check for its thread-link. It has a thread going till node 'B'. So, we make 'B' as our current node in consideration.	B D	D
step-4:	'B' certainly has a left child but its already in our list of visited nodes. So, we print 'B'. Then we check for its right child but it doesn't exist. So, we make its threaded node (i.e 'A') as our current node in consideration.	B D	D B
step-5:	'A' has a left child, 'B', but its already there in the list of visited nodes. So, we print 'A'. Then we check for its right child. 'A' has a right child, 'C' and its not there in our list of visited nodes. So, we add it to that list and we make it our current node in consideration.	B D C	D B A
step-6:	'C' has 'E' as the left child and its not there in our list of visited nodes even. So, we add it to that list and make it our current node in consideration.	B D C E	D B A
		and finally.....	D B E A C

Algorithm:-
Step-1: For the current node check whether it has a left child which is not there in the visited list. If it has then go to step-2 or else step-3.
Step-2: Put that left child in the list of visited nodes and make it your current node in consideration. Go to step-6.
Step-3: For the current node check whether it has a right child. If it has then go to step-4 else go to step-5
Step-4: Make that right child as your current node in consideration. Go to step-6. 
Step-5: Check for the threaded node and if its there make it your current node.
Step-6: Go to step-1 if all the nodes are not over otherwise quit

C implementation:-
struct NODE
{
 struct NODE *left;
 int value;
 struct NODE *right;
 struct NODE *thread;
}

inorder(struct NODE *curr)
{
 while(all the nodes are not over )
   {
    if(curr->left != NULL &&  ! visited(curr->left)) 
      {
       visit(curr->left);
       curr = curr->left;
      }
    else
      {
      printf("%d", curr->value);  
      if(curr->right != NULL) 
         curr = curr->right;
      else
          if(curr->thread != NULL)
              curr = curr->thread;  
      }
   }
}

Note:- The looping condition has to be implemented. You can use your own logic for that. The functions - visited( ) and visit( ) have to be written. visit( ) maintains a linked list of already visited nodes. visited( ) returns a TRUE value if it finds a particular node, in the list maintained by visit( ), otherwise FALSE.

Related Operations:
Trees – concepts
Binary tree creation
Traversals of a binary tree – preorder, inorder and postorder
Binary threaded tree
Non-recursive implementation of traversals
Expressions-to-Trees
Balanced trees / AVL trees – Creation of a balanced binary tree
Balanced m-way tree / B-tree – Creation of a balanced m-way tree