Inorder traversal using constant space – Morris Traversal

Posted on by

Usual approach using linear space (stack)
We can easily do the traversal by using a stack where we keep pushing left. If no left is there then we pop an element to print it and then push its right. This is O(n) time and O(n) space algorithm.

public static void InorderTraversal(BTNode root){
	Stack<BTNode> stack = new Stack<test.BTNode>();
	
	BTNode cur = root;
	while(true){
		//go to left most node while pushing nodes along the way
		if(cur != null){
			stack.push(cur);
			cur = cur.left;
		}
		else{
			//backtrack
			if(!stack.isEmpty()){
				cur = stack.pop();
				System.out.print(cur.key+" ");
				cur = cur.right;
			}
			else{
				return;//done
			}
		}
	}
}

 
Using constant O(1) space – Morris Traversal

Conceptually we want to visit the left subtree and then come back to root to print it and then visit right subtree. If no left node is there then we just want to print root and visit right subtree. Also the in-order traversal of the left subtree ends in the right most node of the left subtree , which is also the predecessor of the root node. So, we can actually access the nodes serially inorder fashion if we had a connection from the right most node to its in-order successor so that we can end up in root right after visiting left subtree. Tree with these kind of connections are called threaded binary tree.

So, we will basically create threaded pointers (predecessor to root) on-the-fly in bottom up manner and then traverse the left subtree. Once traversal is done (i.e. transversal returned to root through threaded pointer) then we can revert back the modification by removing the threaded pointer. Then we can print root and traverse the right subtree in the similar manner. Below is the implementation of this idea that runs in O(n) time and O(1) space.

public static void MorrisInorderTraversal(BTNode root){
	if(root == null){
		return;
	}
	
	BTNode cur = root;
	BTNode pre = null;
	while(cur != null){
		//if no left subtree the visit right subtree right away after printing current node
		if(cur.left == null){
			System.out.print(cur.key+", ");
			cur = cur.right;
		}
		else{
			//otherwise we will traverse the left subtree and come back to current 
			//node by using threaded pointer from predecessor of current node 
			//first find the predecessor of cur
			pre = cur.left;
			while(pre.right != null && pre.right != cur){
				pre = pre.right;
			}
			
			//threaded pointer not added - add it and go to left subtree to traverse
			if(pre.right == null){
				pre.right = cur;
				cur = cur.left;
			}
			else{
				//we traversed left subtree through threaded pointer and reached cur again
				//so revert the threaded pointer and print out current node before traversing right subtree
				pre.right = null;
				System.out.print(cur.key+", ");
				//now traverse right subtree
				cur = cur.right;
			}
		}
	}
}