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 pointer to the node's inorder successor.

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

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.