17 Nov 2013

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 !! :)

2 comments:

  1. Excellent approach! Although I can make small modification to print in-oder predecessor and revert thread, immediately without traversing same left again.

    ReplyDelete
  2. Good post! As far as I know in Binary Search Tree, in-order successor of the input node will also be defined as the node with the smallest key which is greater than the key of input node. So sometimes it’s important to search the next node in sorted order.

    ReplyDelete