Morris Inorder-Traversal

Problem Statement:
    Print inorder traversal of the tree without using extra space (Morris Traversal)
Given Binary Tree

Fig1: Given Binary Tree

Resultant Inorder Traversal:

Fig2: Inorder Traversal of the given Tree

Solution:

Morris Traversal is based on the concept of Threaded Binary Trees. In 1979 , Morris proposed this algorithm in his paper , "Traversing Binary Trees Simple and Cheaply" , i.e. without using any stack and keeping the orginal tree un-altered after the traversal is over.

A binary tree is Threaded by making every left child pointer point to the in-order predecessor of the node and every right child pointer point to the in-order successor of the node.

Advantages:

1. Avoids recursion, which uses a call stack and consumes memory and time.
2. The node keeps a record of its parent.

Disadvantages:

1. The tree is more complex.
2. It is more prone to errors when both the children are not present and both values of nodes point to their ancestors.

Concept Involved: 
      Morris traversal is an implementation of in-order traversal that uses threading:

1. Create links to the in-order successor
2. Print the data using these links
3. Revert the changes to restore original tree.

 Algorithm :

 copy root to current pointer  
 while current is not null  
   if current does not have left child  
     print current data  
     move to right  
   else  
    predessor = current's left child  
         while predessor's right is not null and predessor's right is not current pointer  
           // establishing link , i.e. predessor's right child is null  
               Make current as right child of the rightmost node in temp's left subtree   
               move to left  
          // breaking link , i.e. predessor's right child is current pointer  
               predessor's right = null  
               print current data  
               move current to right  

Full Source Code:  LINK

 /**
 * Inorder Morris Traversal(Threaded Binary Concept used)
 * @author Prateek http://ideone.com/f3lN0T
 */

 public void inorderMorrisTraversal(Node root){
  
  if(root==null)
   return ;
  
  Node current=root;
  while(current!=null){
   
   if(current.left == null)
   {
    System.out.println(current.data); 
    current = current.right;
   }
   else
   {
    Node pre =  current.left;
    while(pre.right != null && pre.right!=current)
     pre = pre.right;
    
    //pre = predessor of current node
    
    if(pre.right==null) //make the link
    {
     pre.right = current ;
     current = current.left;
    }
    else //Break the link
    {
     pre.right = null ;
     System.out.println(current.data);
     current = current.right;
    }
   }
  }
 }

Referernces: http://en.wikipedia.org/wiki/Tree_traversal#Morris_in-order_traversal_using_threading

Similar to this problem is in-order traversal using stack.

Please comment and post your suggestions or any critiques, they are most welcome.  Feel free.

Happy Coding !! :)