Morris traversal allows O(1) space inorder traversal of binary trees. Runtime is still O(n) where n is # of nodes in tree. Based on threaded binary tree.

Binary tree traversal usually takes O(h) space on a (recursive) stack, where h is the height of the tree.

Idea

Create links to in-order successor and print data using these links, then revert changes to restore the tree.

Essentially we are recursively saying, after processing the left subtree, go to the parent but doing this via a link rather than the recursive stack.

Pseudocode

1. Initialize current as root 
2. While current is not NULL
   If current has left child
      a) Make current as right child of the rightmost 
         node in current's left subtree
      b) Go to this left child, i.e., current = current->left
   Else
      a) Print current’s data
      b) Go to the right, i.e., current = current->right

Implementation

class Node:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def morris(node):
    current = node
    while current:
        if not current.left:
            print(current.val)
            current = current.right
            continue

        # find predecessor in left subtree
        prev = current.left
        while prev.right and prev.right != current:
            prev = prev.right

        # set link
        if not prev.right:
            prev.right = current
            current = current.left
            continue

        # undo link to restore tree
        prev.right = None
        print current.val
        current = current.right