Tree: Depth-First Search - Binary Tree Inorder Traversal
Consider this modified Morris inorder traversal code snippet. Which line contains a subtle bug that can cause infinite loops or incorrect output on some trees?
def inorderTraversal(root):
result = []
current = root
while current:
if not current.left:
result.append(current.val)
current = current.right
else:
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if not predecessor.right:
predecessor.right = current # create thread
current = current.left
else:
# BUG: missing line to remove thread
result.append(current.val)
current = current.right
return result
