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