What is the next step for this tree according to morris inorder?

Question

Just before I sat down to write code for morris inorder traversal I tried this example and am a bit confounded as to how its gonna work in this particular case:

       80
    /      \
  60        100
    \       /
     70    90
    /
   65
  / 
 63
  \
   64

Step 1:

   60
    \
     70
   /    \
  65     80
 /        \
63        100
 \         /
  64      90

As far as I understand the algorithm in the next step 70 will become the right child of 65, so what happens to 60? I am pretty sure I am missing something trivial but unfortunately unable to put my finger on it.

public void MorrisInorder() {
    BSTNode<T> p = root, tmp;
    while (p != null)
        if (p.left == null) {
             visit(p);
             p = p.right;
        }
        else {
             tmp = p.left;
             while (tmp.right != null && // go to the rightmost node of
                    tmp.right != p)  // the left subtree or
                  tmp = tmp.right;   // to the temporary parent of p;
             if (tmp.right == null) {// if 'true' rightmost node was
                  tmp.right = p;     // reached, make it a temporary
                  p = p.left;        // parent of the current root,
             }
             else {                  // else a temporary parent has been
                  visit(p);          // found; visit node p and then cut
                  tmp.right = null;  // the right pointer of the current
                  p = p.right;       // parent, whereby it ceases to be
             }                       // a parent;
        }
}

Code I am following for morris inorder traversal.

Answer 1

To directly answer your question, I think the figure is not exact in the step 1 of your case, as the edge from node "80" to node "60" should not be deleted. The only changing in step 1 is just redirect the right point of node "70" to node "80" (see Step 1), which indicates the returning path after the algorithm goes through the left sub-tree of node "80".

Step 1:

      80
    / ^    \
   60 |    100
    \ |    /
    70   90
    /
   65
  / 
 63
  \
  64

After adding the return path from node "70" to node "80", as the left point of current node "60" is NULL, then the current node will be set as node "70". Meanwhile, the right point of node "65" will be redirected to node "70"

Step 2:

      80
    / ^    \
   60 |    100
    \ |    /
    70   90
    /^
   / |
   65
  / 
 63
  \
  64

For more details, the code of morris inorder traversal is listed as follows.

Suppose we have a node structure like:

/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
struct tNode
{
   int data;
   struct tNode* left;
   struct tNode* right;
};

and the traversal is:

/* Function to traverse binary tree without recursion and 
without stack */
void MorrisTraversal(struct tNode *root)
{
  struct tNode *current,*pre;

  if(root == NULL)
     return; 

  current = root;
  while(current != NULL)
  {
    /* This means there is no left sub-tree for current node,
       then just print current node, and go to the right "child" node.
       The right "child" node may be either its true child node,
       or the returning path for "60" sub-tree (like "70" to "80") */
    if(current->left == NULL)
    {
      printf(" %d ", current->data);
      current = current->right;      
    }    
    else
    {
      /* before going to the left sub-tree, we need to find a returning path
         to current node (such as when current node is "80", and we want to 
         go to "60", so we need to save the returning path from left sub-tree 
         to "80"). It is easy to imagine that we need to return to the current
         node when we arriving the right-most node of current left sub-tree.
         Therefore, we just go to the right-most node (the first condition in
         while) and set the returning path at "pre->right == NULL" block, as
         well as updating the current node. Another situation is that when we
         arrive at the left-most leaf node (if not exist, it means current->left
         is NULL, and we won't go into this block), we have already set the right
         point of left-most leaf node as the returning node (it un-satisfies the
         second condition of while loop), and then we will recover the right
         point of this leaf node in the next "else" block.
          */
      pre = current->left;
      while(pre->right != NULL && pre->right != current)
        pre = pre->right;

      /* Make current as right child of its inorder predecessor */
      if(pre->right == NULL)
      {
        pre->right = current;
        current = current->left;
      }

      /* Revert the changes made in if part to restore the original 
        tree i.e., fix the right child of predecssor */   
      else `enter code here`
      {
        pre->right = NULL;
        printf(" %d ",current->data);
        current = current->right;      
      } /* End of if condition pre->right == NULL */
    } /* End of if condition current->left == NULL*/
  } /* End of while */
}