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