Morris In-Order Traversal
by 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";

    //load data into tree
    int[] treeTape = {50, 25, 75, 12, 40, 62, 87};
    for (int i : treeTape) {
      bst.add(i);
    }
    assertEquals(treeTape.length, bst.size());//has correct size

    //test morrisInorder
    output.reset();
    bst.morrisInorder();//prints to standard output
    assertEquals(expected, output.toString());
    assertEquals(treeTape.length, bst.size());//has correct size
    System.setOut(new PrintStream(new FileOutputStream(FileDescriptor.out)));
    System.out.println("done with morrisInorder");
  }
}