# Python: Morris Iterator and Normal Iterator. Question(solved now) is why it is TLE if I uncomment the "break". Be careful when using morris traversal since you cannot break in midway.

• Morris iterator and normal iterator solution.

On my own computer they work both well.

However, in the online judge system, if you uncomment the "break" line, the online system reports TLE. It only happens when I use Morris Iterator.

I cannot figure out why.
Who can help me with it?

Thanks a lot!

``````
class Solution(object):
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""

## Morris Traversal (O(n))
def inOrderIter_Morris(cur):
while cur:
if not cur.left:
yield cur
cur = cur.right
else:
# find the predecesser of cur
pred = cur.left
while pred.right and pred.right != cur: # make sure it is not a loop which means it is visited
pred = pred.right
if not pred.right:
pred.right = cur
cur = cur.left
else:
yield cur
cur = cur.right
pred.right = None

## use recursive iterator, not sure about the memory usage. (O(n)?)
def inOrderIter(root):
if root:
for node in inOrderIter(root.left):
yield node
yield root
for node in inOrderIter(root.right):
yield node

# main: find the one or two unordered pairs and swap them
prev, first = None, None
for node in inOrderIter_Morris(root):
# for node in inOrderIter(root):
if prev and prev.val > node.val:
if not first:
first = prev
second = node
else:
second = node
#break # if you uncomment this line you'll get TLE
prev = node
first.val, second.val = second.val, first.val``````

• I kind of figured out why. If I use break, the modified tree will not be restored so the judge system cannot judge it due to the loop in the tree.

• We need to be very careful when we use morris traversal since it modifies the tree, which means we could only do a complete traversal without break. Make sure to restore it.

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