### Iterative Inorder

void fnIterativeInorderBT (TreeNodePtr psNode)
{
while (TRUE)
{
for (; NULL != psNode; psNode = psNode->psLeftChild)
{
fnPushStack (psNode);
}
if (fnIsEmptyStack ())
{
break;
}
else
{
psNode = fnPopStack ();
}
printf ("%d", psNode->data);
psNode = psNode->psRightChild;
}
}

### Threaded Binary Trees

A binary tree with n nodes usually has n + 1 NULL nodes. The idea of a threaded binary tree is to replace these NULL pointers with pointers to nodes in the tree to aid in the preorder, inorder, and postorder traversals of a binary tree. A nonrecursive tree traversal algorithm results from using threads.
For purposes of this discussion we will define the following terms:

1) left inthreaded - each node that has a NULL left child is replaced with a pointer to the node's inorder predecessor.

2) right inthreaded - each node that has a NULL right child is replaced with a ponter to the node's inorder successor.

3) inthreaded - is a tree that is both left and right inthreaded.

P#1: For the BST created in P#1, create a right inthreaded BST.

Let's take a look at a possible iterative inorder tree traversal algorithm implemented in C using threads.

void fnThreadedInorderBT (TreeNodePtr psNode)
{
TreeNodePtr psTemp = psNode;
while (NULL != psTemp)
{
while (NULL != psTemp->psLeftChild)
{
psTemp = psTemp->psLeftChild;
}
printf ("%d", psTemp->data);
while (TRUE == psTemp->rightThread)
{
psTemp = psTemp->psRightChild;
printf ("%d", psTemp->data);
}
psTemp = psTemp->psRightChild;
}
}

P#2: Create an inthreaded tree for the above data.
P#3: Would the above algorithm algorithm work on an inthreaded tree? Why or why not?

P#4: If not, fix the above C function to handle an inthreaded tree.