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.