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.
function morrisInorder(root):
current = root
while current:
if current.left == null:
process(current)
current = current.right
else:
// Find predecessor
pred = current.left
while pred.right and pred.right != current:
pred = pred.right
if pred.right == null:
// 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.