Morris traversal achieves space by temporarily modifying the tree. The idea: use the rightmost node of the left subtree to point back to the current node.
def morrisInorder(root):
current = root
while current:
if not current.left:
process(current)
current = current.right
else:
# Find predecessor
pred = current.left
while pred.right and pred.right != current:
pred = pred.right
if not pred.right:
# Create thread
pred.right = current
current = current.left
else:
# Remove thread
pred.right = null
process(current)
current = current.right
Time: . Space: . Useful when stack space is limited.