Tree: Depth-First Search - Binary Tree Inorder Traversal
Given the following Morris inorder traversal code, what is the final output list after running
Tree structure:
2
/ \ 1 3
inorderTraversal on this tree?Tree structure:
2
/ \ 1 3
from typing import Optional, List
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
result = []
current = root
while current:
if not current.left:
result.append(current.val) # visit node
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:
predecessor.right = None # remove thread
result.append(current.val) # visit node
current = current.right
return result
