# Morris In-Order Traversalby Isai Damier, Android Engineer @ Google

```/***********************************************************************
* Author: Isai Damier
* Title: Morris In-Order Traversal
* Project: geekviewpoint
* Package: algorithms
*
* Time Complexity of Solution:
*   Best = Average = Worst = O(n).
*
* Strategy:
*   Normally you need a stack or a queue to traverse a tree.  But
*   there are other options whereby you temporarily restructure the
*   tree. Joseph M. Morris devised one such methods. In Morris'
*   algorithm, a tree is restructured so that the tree has no left
*   child. And with no left child, in-order traversal is trivialized
*   from the usual LVR to a mere VR (visit then go right).
*
*   Morris's algorithm goes like this
*
*     while not done
*       if node has no left child
*          visit node;
*          go to right child;
*       else
*          make node the right child of its predecessor;
*          go to the left descendent;
*
**********************************************************************/
public void morrisInorder() {
Node parent = root, tmp;
while (null != parent) {
if (null == parent.left) {
visit(parent);
parent = parent.right;
} else {
tmp = parent.left;
while (null != tmp.right && parent != tmp.right) {
tmp = tmp.right;
}
if (null == tmp.right) {
tmp.right = parent;
parent = parent.left;
} else {
visit(parent);
tmp.right = null;
parent = parent.right;
}
}
}
}```
```import org.junit.Test;
import static org.junit.Assert.*;

public class BSTTest {

/**
* Test of morrisInorder method, of class BST.
*/
@Test
public void testMorrisInorder() {
System.out.println("morrisInorder");
final ByteArrayOutputStream output = new ByteArrayOutputStream();
System.setOut(new PrintStream(output));

BST bst = new BST();

String expected = "";
assertEquals(expected, output.toString());
expected = "12\n25\n40\n50\n62\n75\n87\n";

int[] treeTape = {50, 25, 75, 12, 40, 62, 87};
for (int i : treeTape) {