Morris InOrder Tree Traversal, Tree Traversal without using extra space and without recursion

We have the regular tree traversals that uses either recursion (function stack), or intentionally created stack to do the traversal in iterative way. But what do we do when we need to do a tree traversal without any extra space and without recursion.
Lets first think this way, iterative way is possible if we create a stack (this is a regular way). If we give some thought, we need stack for storing the in-order successor, we push the current node into stack and move to left, when we come back , we pop this node and print, and then move right.
Can we think of getting to this node back by some way. Does Threaded Binary Tree ring any bells? Yes, we can create threads back to the in-order successor, and in this way we will get to use the space (null pointers) of leaf nodes, and wont be needing any extra space.

So, Morris InOrder Traversal uses Threads instead of stack to get to the in-order successor. In this traversal, we first create threads to in-order successor, and print the nodes, and by the end we revert back the changes made to tree, i.e we remove all the additional threads we created in the process. Point to be noted is that, tree is modified in between, but by the end of traversal, original tree is restored.

Algorithm:
take root node into new node temp
while temp is not null
   if temp does not have left child
       print temp data
       move to right
   else
       Make temp as right child of the rightmost node in temp's left subtree 
       move to left

Here’s the C++ code

//Binary Tree
typedef struct bTree{
    int data;
    bTree *left,*right;
}bTree;
//MORRIS INORDER TRAVERSAL, pass the root node as argument
void morris(bTree *ptr){
    //testing part :P
    if(!ptr){
        return;
    }
    // we do have a genuine bTree

    bTree *temp;//temp pointer

    //loop till ptr is null
    while(ptr){
        // if ptr left is null
        if(!ptr->left){
            //print the data
            printf("[%d]",ptr->data);
            //move right
            ptr=ptr->right;
        }else{//has a left pointer

            //Find the inorder predecessor of current node
            temp = ptr->left;
            while(temp->right && temp->right!=ptr){
                temp=temp->right;
            }

            //Make current node as right child of its inorder predecessor
            if(!temp->right){
                temp->right=ptr;
                ptr=ptr->left;
            }else{
                // Revert the changes to restore the original tree
                temp->right = NULL;//make it the way it was earlier, i.e null
                printf("[%d]",ptr->data);
                ptr=ptr->right;
            }

        }//end if else
    }//end while
}//end func morris

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s