Morris Traversal

Morris traversal achieves $O(1)$ 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: $O(n)$. Space: $O(1)$. Useful when stack space is limited.