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;
  #
  #=======================================================================
 
 
class BST( object ):

  def __init__( self ):
      self.root = None

  def morrisInorder( self ):
    parent, tmp = self.root, None
    while None != parent:
      if None == parent.left:
        self.visit( parent );
        parent = parent.right
      else:
        tmp = parent.left
        while None != tmp.right and parent != tmp.right:
          tmp = tmp.right

        if None == tmp.right:
          tmp.right = parent
          parent = parent.left
        else:
          self.visit( parent )
          tmp.right = None
          parent = parent.right
 import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):
 #=====================================================================
  # Test of morrisInorder method, of class BST.
  #=====================================================================
  def testMorrisInorder( self ):
    bst = BST()

    old_stdout = sys.stdout
    result = sys.stdout = StringIO()

    expected = ""
    self.assertEquals( expected, result.getvalue() )
    expected = "12\n25\n40\n50\n62\n75\n87\n"

    # load data into tree
    treeTape = [50, 25, 75, 12, 40, 62, 87]
    for i in treeTape:
      bst.add( i )

    self.assertEquals( len( treeTape ), bst.size() ) # has correct size

    # test morrisInorder
    result = sys.stdout = StringIO()
    bst.morrisInorder() # prints to standard output
    self.assertEquals( expected, result.getvalue() )
    self.assertEquals( len( treeTape ), bst.size() ) # has correct size
    sys.stdout = old_stdout
    print "done with testMorrisInorder"