Write a non-recursive traversal of a Binary Search Tree using constant space and O(n) run time

How about Morris Inorder tree traversal? Its based on the notion of threaded trees and it modifies the tree, but reverts it back when its done.

Linkie: http://geeksforgeeks.org/?p=6358

Doesn’t use any extra space.