this is elegant algorithm from Morris for stackless inorder
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;
}
/* 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 */
}
outline of what it does
1. take a root node
2. assign into some temporary variable like current
3. check if current is non-null
4. now start a loop until this current is non-null
5. check if current->left is non-null and store in another variable pre
6. if current->left is null, assign current as current->right.
7. otherwise assign pre as current->left
8. start a loop to until you hit either pre->right == null or pre->right == current
9. what it means is that you got successor of current if pre->right == null otherwise you hit the temporary thread created by yourself previously
10. if pre->right == null, create a temp thread , assign pre->right = current, current = current->left
11. if pre->right == current, current = current->right and pre->right = null
