morris_tree_traversal.py

def morris_tree_traversal(root):
  current = root
  result = []
  while current is not None:
    if current.left is None:
      result.append(current.val)
      current = current.right
    else:
      pre = current.left
  while(pre.right is not None and pre.right is not current):
    pre = pre.right
    if pre.right is None:
      pre.right = current
      current = current.left
    else:
      pre.right = None
      result.append(current.val)
      current = current.right
  return result