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.


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.


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
      a) Print current’s data
      b) Go to the right, i.e., current = current->right


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:
            current = current.right

        # 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

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