# 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;
}

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)``````