Morris InOrder Traverse Algorithm

MorrisInOrderTraverse.java

public static void morrisInOrderTraverse(TreeNode root){
    	TreeNode ptr = root;
	while (ptr != null){
		if (ptr.left == null){
			visit(ptr);
			ptr = ptr.right;
		}else{
			TreeNode node = ptr.left;
			while (node.right != null && node.right != ptr)
				node = node.right;
			if (node.right == null){
				node.right = ptr;
				ptr = ptr.left;
			}else{
				visit(ptr);
				node.right = null;
				ptr = ptr.right;
			}
		}
	}
}