Binary Tree Binay Tree

Program – Inorder Tree Traversal without recursion and without stack!

order
order
Inorder Tree Traversal without recursion and without stack! - Using Morris Traversal, we can traverse the tree without using stack and recursion.

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.

1. Initialize current as root 
2. While current is not NULL
   If current does not have left child
      a) Print current’s data
      b) Go to the right, i.e., current = current->right
   Else
      a) Make current as right child of the rightmost 
         node in current's left subtree
      b) Go to this left child, i.e., current = current->left

Although the tree is modified through the traversal, it is reverted back to its original shape after the completion. Unlike Stack based traversal, no extra space is required for this traversal.

// Java program to print inorder traversal without recursion and stack
  
/* A binary tree tNode has data, pointer to left child
   and a pointer to right child */
class tNode 
{
    int data;
    tNode left, right;
      
    tNode(int item) 
    {
        data = item;
        left = right = null;
    }
}
  
class BinaryTree 
{
    tNode root;
  
    /* Function to traverse binary tree without recursion and 
       without stack */
    void MorrisTraversal(tNode root) {
        tNode current, pre;
          
        if (root == null)
            return;
          
        current = root;
        while (current != null) 
        {
            if (current.left == null) 
            {
                System.out.print(current.data + " ");
                current = current.right;
            }
            else
            {
                /* Find the inorder predecessor of current */
                pre = current.left;
                while (pre.right != null && pre.right != current) 
                    pre = pre.right;
                 
                /* Make current as right child of its inorder predecessor */
                if (pre.right == null) 
                {
                    pre.right = current;
                    current = current.left;
                } 
  
                 /* Revert the changes made in if part to restore the 
                    original tree i.e.,fix the right child of predecssor*/
                 else
                 {
                    pre.right = null;
                    System.out.print(current.data + " ");
                    current = current.right;
                }   /* End of if condition pre->right == NULL */
                  
            } /* End of if condition current->left == NULL*/
              
        } /* End of while */
          
    }
      
    public static void main(String args[]) 
    {
        /* Constructed binary tree is
               1
             /   \
            2      3
          /  \
        4     5
        */
        BinaryTree tree = new BinaryTree();
        tree.root = new tNode(1);
        tree.root.left = new tNode(2);
        tree.root.right = new tNode(3);
        tree.root.left.left = new tNode(4);
        tree.root.left.right = new tNode(5);
          
        tree.MorrisTraversal(tree.root);
    }
}
  
// This code has been contributed by Mayank Jaiswal(mayank_24)

Output:

4 2 5 1 3
READ  C Algorithm - Iterative Postorder Traversal | Set 1 (Using Two Stacks)

About the author

Venkatesan Prabu

Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

Add Comment

Click here to post a comment