**Morris Algorithm - O(n) time and O(1) space algorithm to traverse the tree**

This algorithm is to change the structure of the tree to find the next node to be traverse, the steps are listed below:

- set curNode to root
- if
`curNode.left`

is None, output`curNode.val`

and set`curNode`

to`curNode.right`

- if
`curNode.left`

is not None, find`prevNode`

of`curNode`

in its left subtree- if
`prevNode.right`

== None, set prevNode.right to curNode - if
`prevNode.right`

==`curNode`

, set`prevNode.right`

back to None, output`curNode`

, and update`curNode`

to`curNode.right`

- if
- loop step 1 and 2 until
`curNode`

is None

**Node**: `preNode`

of curNode in the Steps refers to the node that is adjacently before `curNode`

in the output list of the inorder traversal of the given tree.

```
def inorderTraversal(self, root):
def _findRightmost(root, parent):
tmp = root
while tmp.right and tmp.right != parent:
tmp = tmp.right
return tmp
if not root: return []
ans = []
curNode = root
while curNode:
if curNode.left:
prevNode = _findRightmost(curNode.left, curNode)
if prevNode.right == curNode:
prevNode.right = None
ans.append(curNode.val)
curNode = curNode.right
else:
prevNode.right = curNode
curNode = curNode.left
else:
ans.append(curNode.val)
curNode = curNode.right
return ans
```

Morris Reference: http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

**Clean iterative normal algorithm in Python**

`thisNode`

stores the node that has not been traversed

`stack`

stores the node whose left sub-tree has been or will be traversed.

- if there is a node that has not been traversed at all, we push it into
`stack`

and then traverse its left subtree. - if there is no node that has not been traversed at all, then we pop one node from the
`stack`

and then start to traverse its right-subtree.

```
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
thisNode = root # store the node has not been traversed yet
stack = [] # store the node whose left subtree has been traversed
ans = []
while thisNode or stack:
while thisNode:
stack.append(thisNode)
thisNode = thisNode.left
if stack:
thisNode = stack.pop(-1)
ans.append(thisNode.val)
thisNode = thisNode.right
return ans
```