# 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"

treeTape = [50, 25, 75, 12, 40, 62, 87]
for i in treeTape: