Morris Traversal ( Threaded Binary Tree )

PROBLEM :

Inorder Tree Traversal without recursion and without stack!

Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
/*
typedef struct BST
{
int info ;
struct BST *left ;
struct BST *right ;
}tree ;------------------------------*/


void Morris_tree_traversal(tree *root)
{
if(root==NULL)
return ;

tree *current,*prev ;
current=root ;

while(current!=NULL)
{
if(current->left==NULL)
{
cout<<current->info<<" " ;
current=current->right ;
}
else
{
prev=current->left ;
while(prev->right!=NULL&&prev->right!=current)
prev=prev->right ;

if(prev->right==NULL)
{
prev->right=current ;
current=current->left ;
}
else
{
prev->right=NULL ;
cout<<current->info<<" " ;
current=current->right ;
}
}
}
}

---------------------------------------------------------------------------------