Explain Morris inorder tree traversal without using stacks or recursion

Question

Can someone please help me understand the following Morris inorder tree traversal algorithm without using stacks or recursion ? I was trying to understand how it works, but its just escaping me.

 1. Initialize current as root  2. While current is not NULL   If current does not have left child         a. Print current’s data    b. Go to the right, i.e., current = current->right   Else    a. In current's left subtree, make current the right child of the rightmost node    b. Go to this left child, i.e., current = current->left 

I understand the tree is modified in a way that the current node, is made the right child of the max node in right subtree and use this property for inorder traversal. But beyond that, I'm lost.

EDIT: Found this accompanying c++ code. I was having a hard time to understand how the tree is restored after it is modified. The magic lies in else clause, which is hit once the right leaf is modified. See code for details:

/* 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)   {     if(current->left == NULL)     {       printf(" %d ", current->data);       current = current->right;     }     else     {       /* Find the inorder predecessor of current */       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;       }       // MAGIC OF RESTORING the Tree happens here:        /* Revert the changes made in if part to restore the original         tree i.e., fix the right child of predecssor */       else       {         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 */ } 

Answer 1

If I am reading the algorithm right, this should be an example of how it works:

     X    /   \   Y     Z  / \   / \ A   B C   D 

First, X is the root, so it is initialized as current. X has a left child, so X is made the rightmost right child of X's left subtree -- the immediate predecessor to X in an inorder traversal. So X is made the right child of B, then current is set to Y. The tree now looks like this:

    Y    / \   A   B        \         X        / \      (Y)  Z          / \         C   D 

(Y) above refers to Y and all of its children, which are omitted for recursion issues. The important part is listed anyway. Now that the tree has a link back to X, the traversal continues...

 A   \    Y   / \ (A)  B       \        X       / \     (Y)  Z         / \        C   D 

Then A is outputted, because it has no left child, and current is returned to Y, which was made A's right child in the previous iteration. On the next iteration, Y has both children. However, the dual-condition of the loop makes it stop when it reaches itself, which is an indication that it's left subtree has already been traversed. So, it prints itself, and continues with its right subtree, which is B.

B prints itself, and then current becomes X, which goes through the same checking process as Y did, also realizing that its left subtree has been traversed, continuing with the Z. The rest of the tree follows the same pattern.

No recursion is necessary, because instead of relying on backtracking through a stack, a link back to the root of the (sub)tree is moved to the point at which it would be accessed in a recursive inorder tree traversal algorithm anyway -- after its left subtree has finished.