What is Morris traversal?

Morris (InOrder) traversal is a tree traversal algorithm that does not employ the use of recursion or a stack. In this traversal, links are created as successors and nodes are printed using these links. Finally, the changes are reverted back to restore the original tree.

Algorithm

• Initialize current as root

• While current is not NULL

  • If the current does not have left child:

    • Print current’s data
    • Go to the right, i.e., current = current->right

  • Else:

    • Find rightmost node in current left subtree OR node whose right child == current.

    • If we found right child == current

    • Go to the right, i.e. current = curent->right

    • Else

    • Make current as the right child of that rightmost node we found;

    • Go to this left child, i.e., current = current->left

CODE

// Java program to print inorder 
// traversal without recursion
// and stack

/* A binary tree tNode has data,
a 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 a 
    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 the 'if' part
                to restore the original 
                tree i.e., fix
                the right child of predecessor*/
                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 */
    }

    // Driver Code
    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)

Reference links:
https://www.cnblogs.com/anniekim/archive/2013/06/15/morristraversal.html
https://www.educative.io/edpresso/what-is-morris-traversal
https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/