Morris Traversal Binary Tree Inorder (without Recursion or Stack)

Inorder is one of the ways to traverse a binary tree in depth first fashion. We have already discussed Inorder Traversal (Left, Root, Right) of a binary thee in our previous articles using recursive approach and using stack (without recursion). But in this article we will discuss Morris Traversal which is used to traverse a Binary Tree without using recursion or Stack.

If you are interested in Inorder traversal using recursion or iterative approach using Stack, refer below articles -
Tree Traversal - Depth First (Iterative/ Non Recursive Approach)
Tree Traversals - Depth First (Recursive Approach)

Explanation Morris Traversal - Suppose we have a binary tree as shown in the figure below.

Now we already know that Inorder traversal follows this order - Left, Root, Right.
And this sequence must be followed by all the sub trees as well.

In-order traversal of this Tree would be - 2 3 4 5 6 8 10

In this sequence we can clearly see that after visiting the left node or left sub tree we need a way to come back to its root node so that we can print it and go to the right sub tree/ node. For example - In above binary tree if we start from root node 5 first we will visit the left sub tree (2, 3, 4) then Root Node (5) and then Right Sub tree (6, 8, 10). But after visiting the left sub tree (2, 3, 4) we need a pointer to come back to the root node(5) of this sub tree(2, 3, 4), If we somehow manage to do so we can easily visit the Root node and then Right sub tree.

To achieve this for every node (which could be root node of a subtree) we visit we will set its pointer in its left sub tree so that we can come back to it when left sub tree traversal is done.
Now the question is how to set the pointer ?
Well we know that left sub tree would also be traversed in In-order (Left, Root, Right), so if we hit the right most Node of the sub tree during traversal of the sub tree we can say that sub tree traversal is complete and its time to go back to the Root node. So we can see that right most node of a sub tree is the right place to save the pointer back to the Root node.
In Morris traversal we will be doing the same, saving the root node pointer in the right most node of its left sub tree.
Also don't forget to remove this extra pointer when we reach the root node using the pointer, that will keep the original tree intact. 

So After setting the pointers back to the root node our tree would look like this.

Implementation -

package ds.tree;

import ds.tree.BStree.Node;

public class MorrisTraversal {
	
	public static void inOrder(Node root) {
		Node pre;
		while(root != null) {
			if(root.left == null) {
				System.out.print(root.data + " ");
				root = root.right;
			}else {
				pre = root.left;
				while(pre.right != null && pre.right != root) {
					pre = pre.right;
				}
				if(pre.right == null) {
					pre.right = root;
					root = root.left;
				}else {
					pre.right = null;
					System.out.print(root.data + " ");
					root = root.right;
				}
			}
		}
	}
}

Custom Binary Tree (BST) class-

package ds.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BStree {

	private Node root;

	public Node getRoot() {
		return root;
	}

	public BStree(int rootData) {
		this.root = new Node(rootData);
	}
	
	public BStree(Node root) {
		this.root = root;
	}

	static class Node {
		int data;
		Node left;
		Node right;

		public Node(int data) {
			this.data = data;
		}
	}

	public void insert(int data) {
		Node nNode = new Node(data);
		
		Node root = this.root;
		Node nodeB = null;
		while (root != null) {
			nodeB = root;
			if (root.data > data) {
				root = root.left;
			} else {
				root = root.right;
			}
		}
		if(data < nodeB.data)
			nodeB.left = nNode;
		else
			nodeB.right = nNode; 
	}
	
	public void printInOrder() {
		inOrderRec(this.root);
	}
	
	private void inOrderRec(Node root){
		if(root == null)
			return;
		inOrderRec(root.left);
		System.out.print(root.data + " ");
		inOrderRec(root.right);
	}
}

This custom BST contains one method printInOrder() which will print the tree using in-order traversal using recursive approach, we will use this method to compare the output with Morris Traversal.

Main class -

package ds.tree;

public class BtreeMain {
	
	public static void main(String[] args) {
		BStree bst = new BStree(5);
		bst.insert(3);
		bst.insert(8);
		bst.insert(6);
		bst.insert(4);
		bst.insert(2);
		bst.insert(10);
		
		System.out.println("Iterative Inorder -");
		bst.inorderIterative();
		
		System.out.println("\nMorris Inorder -");
		MorrisTraversal.inOrder(bst.getRoot());
	}
}

Output -
Iterative Inorder -
2 3 4 5 6 8 10 
Morris Inorder -
2 3 4 5 6 8 10

So now we know one more iterative implementation to traverse a Binary Tree which does not use Stack or any other data atructure.