Make delicious recipes!

Print In-Order traversal without recursion and stack

InOrder traversal means Left, Root, Right

Thus once left subtree is fully exhausted, we print the parent and then move on to right subtree. But since the left subtree does not have a parent pointer, then we cannot come back to the parent after subtree has been traversed.

Also, note the following:

1) Parent of left subtree is inorder successor of the left subtree.

2) We do not need to get back to parent after traversing right subtree.


So if we somehow determine the inorder successor of a subtree when that subtree is fully traversed, then we shall be able to traverse the tree fully.

Normally, this purpose is solved by a stack.

But we can also temporarily make the tree a threaded binary tree (while traversing itself) and avoid the use of a stack.

void MorrisTraversal (Node root) 
{
    Node curr = root;
    while (curr != null)
    {
        if (curr.left != null) 
        {
            // find inorder predecessor of left subtree
            Node pre = curr.left;
            while (pre.right != null && pre.right != curr) 
            {
                pre = pre.right;
            }
            if (pre.right == null) 
            {
                // Threaded property for this node was not set. Set it now
                pre.right = curr;
                curr = curr.left; // Thread created. Switch to this subtree now
            } else 
            {
                // This means pre.right = curr
                // Which implies that thread for this was set already, 
                // So we do not need to traverse this subtree again
                pre.right = null; // reset the thread we created earlier
                print (curr); 
                curr = curr.right;
            }
        } else 
        {
            // no left subtree, print yourself and get to right subtree
            print (curr); 
            // we will never get right=null till the end because of above threads
            curr = curr.right; 
        }
    }
}
Morris traversal shown above avoids the use of a stack but is also more time consuming since we need to traverse the tree for creating and deleting threads.

For a subtree with ‘N’ nodes, one has to traverse approximately logN nodes to create/delete the thread.

However, that time can be thought of as comparable to the creation of new nodes, push and pop operations in the stack.




Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal