**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 the `root` as the current node `curr`.

- While `curr` is *not* `NULL`, check if `curr` has a left child.

- If `curr` does not have a left child, print `curr` and update it to point to the node on the right of `curr`.

- Else, make `curr` the right child of the rightmost node in `curr`'s left subtree. 

- Update `curr` to this left node.



# Demo

Let's take the binary tree given below and traverse it using Morris (InOrder) traversal.

$4$ is the root, so it is initialized as `curr`. $4$ has a left child, so it is made the rightmost right child of it's left subtree (the immediate predecessor to $4$ in an InOrder traversal). Finally, $4$ is made the right child of $3$ and `curr` is set to $2$.

Now the `curr` is on $2$ and  has a left child and right child is already linked to root. So we move the `curr` to $1$. `curr` has no left and right child. Right will be linked to the root $2$

$1$ is printed because it has no left child and `curr` is returned to $2$, which was made to be $1$'s right child in the previous iteration. On the next iteration, $2$ has both children. However, the dual-condition of the loop makes it stop when it reaches itself; this is an indication that its left subtree has already been traversed. So, it prints itself and continues with its right subtree $3$. $3$ prints itself, and `curr` becomes $3$ and goes through the same checking process that $2$ did. It also realizes that its left subtree has been traversed and continues with the $4$. The rest of the tree follows this same pattern.

# Code

The above algorithm is implemented in the code below:

#include <iostream>
using namespace std; 

struct Node { 
	int data; 
	struct Node* left_node; 
	struct Node* right_node; 
}; 

void Morris(struct Node* root) 
{ 
	struct Node *curr, *prev; 

	if (root == NULL) 
		return; 

	curr = root; 

	while (curr != NULL) { 

		if (curr->left_node == NULL) { 
			cout << curr->data << endl; 
			curr = curr->right_node; 
		} 

		else { 

			/* Find the previous (prev) of curr */
			prev = curr->left_node; 
			while (prev->right_node != NULL && prev->right_node != curr) 
				prev = prev->right_node; 

			/* Make curr as the right child of its
			previous */
			if (prev->right_node == NULL) { 
				prev->right_node = curr; 
				curr = curr->left_node; 
			} 

			/* fix the right child of previous */
			else { 
				prev->right_node = NULL; 
				cout << curr->data << endl; 
				curr = curr->right_node; 
			} 
		} 
	} 
} 

struct Node* add_node(int data) 
{ 
	struct Node* node = new Node; 
	node->data = data; 
	node->left_node = NULL; 
	node->right_node = NULL; 

	return (node); 
} 

int main() 
{ 

	struct Node* root = add_node(4); 
	root->left_node = add_node(2); 
	root->right_node = add_node(5); 
	root->left_node->left_node = add_node(1); 
	root->left_node->right_node = add_node(3); 
	Morris(root); 
	return 0; 
} 

class Node: 
	def __init__(self, data): 
		self.data = data 
		self.left_node = None
		self.right_node = None

def Morris(root): 
	# Set current to root of binary tree 
	curr = root 
	
	while(curr is not None): 
		
		if curr.left_node is None: 
			print curr.data, 
			curr = curr.right_node 
		else: 
			# Find the previous (prev) of curr 
			prev = curr.left_node 
			while(prev.right_node is not None and prev.right_node != curr): 
				prev = prev.right_node 

			# Make curr as right child of its prev 
			if(prev.right_node is None): 
				prev.right_node = curr 
				curr = curr.left_node 
				
			# fix the right child of prev
			else: 
				prev.right_node = None
				print curr.data, 
				curr = curr.right_node 
			

root = Node(4) 
root.left_node = Node(2) 
root.right_node = Node(5) 
root.left_node.left_node = Node(1) 
root.left_node.right_node = Node(3) 

Morris(root) 



Python

class Node { 
	int data; 
	Node left_node, right_node; 

	Node(int item) 
	{ 
		data = item; 
		left_node =  null;
		right_node = null; 
	} 
} 

class Tree { 
	Node root; 

	void Morris(Node root) 
	{ 
		Node curr, prev; 

		if (root == null) 
			return; 

		curr = root; 
		while (curr != null) { 
			if (curr.left_node == null) { 
				System.out.print(curr.data + " "); 
				curr = curr.right_node; 
			} 
			else { 
				/* Find the previous (prev) of curr */
				prev = curr.left_node; 
				while (prev.right_node != null && prev.right_node != curr) 
					prev = prev.right_node; 

				/* Make curr as right child of its prev */
				if (prev.right_node == null) { 
					prev.right_node = curr; 
					curr = curr.left_node; 
				} 

				/* fix the right child of prev*/

				else { 
					prev.right_node = null; 
					System.out.print(curr.data + " "); 
					curr = curr.right_node; 
				} 

			} 

		}
	} 

	public static void main(String args[]) 
	{ 
		
		Tree tree = new Tree(); 
		tree.root = new Node(4); 
		tree.root.left_node = new Node(2); 
		tree.root.right_node = new Node(5); 
		tree.root.left_node.left_node = new Node(1); 
		tree.root.left_node.right_node = new Node(3); 

		tree.Morris(tree.root); 
	} 
} 

Java

What is Morris traversal?

Morris traversal performs tree traversal without recursion or stacks by creating temporary links, printing nodes, and then restoring the tree.