# inorder, preorder, postorder, Morris traversal with O(1) space and O(n) time

• Morris Traversal is a way of traversing BST with O(1) space and O(n) time. It's a little hard to understand but the basic idea is to link predecessor back to current node so that we can trace back to top of BST. It's also a little tricky to see how it is O(n) since finding predecessor is often O(logn). The answer is , we don't have to find predecessor for every node, only the nodes with valid left child. It will be obvious if you draw a tree to see that every edge is only visited constant time.

Inorder

``````    def inorderTraversal(self, root):
result=[]
node=root
while node!=None:
if node.left==None:
result.append(node.val)
node=node.right
else:
pre=node.left
while pre.right!=None and pre.right!=node:
pre=pre.right
if pre.right==None:
pre.right=node
node=node.left
else:
pre.right=None
result.append(node.val)
node=node.right
return result
``````

Preorder, basically the same, just one line of change

``````    def preorderTraversal(self, root):
result=[]
node=root
while node!=None:
#print(node.val)
if node.left==None:
result.append(node.val)
node=node.right
else:
pre=node.left
while pre.right!=node and pre.right!=None:
pre=pre.right
if pre.right==None:
result.append(node.val)
pre.right=node
node=node.left
else:
pre.right=None
node=node.right
return result
``````

Postorder, this is a little tricky, you have to output path along predecessor in reverse order.

``````    def postorderTraversal(self, root):
result=[]
def reverseOrder(left,right):
while left<right:
result[left],result[right]=result[right],result[left]
left+=1
right-=1
dummynode= TreeNode(None) #dummy node
node=dummynode
node.left=root
while node!=None:
print(node.val)
if node.left==None:
node=node.right
else:
pre=node.left
while pre.right!=None and pre.right!=node:
pre=pre.right
if pre.right==None:
pre.right=node
node=node.left
else:
pre=node.left
count=1
while pre.right!=None and pre.right!=node:
result.append(pre.val)
pre=pre.right
count+=1
result.append(pre.val)
pre.right=None
reverseOrder(len(result)-count,len(result)-1)
node=node.right

return result
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.