# Morris Traversal

**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
```