# Binary Tree Inorder Traversal ## # Definition for a Binary Tree Node

``````class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
``````

## # Solution

### # Recursion

``````def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def helper(node: TreeNode):
if node:
helper(node.left)
res.append(node.val)
helper(node.right)
helper(root)
return res
``````

Recursive solution is trivial, could you do it iteratively?

### # Interation

``````def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
curr = root
while stack or curr:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
res.append(curr.val)
curr = curr.right
return res
``````

### # Morris Traversal

• Initialize current as root
• While current is not NULL
• If current does not have left child
2. Go to the right, i.e., current = current.right
• Else
1. In current's left subtree, make current the right child of the rightmost node
2. Go to this left child, i.e., current = current.left
``````def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
curr = root
while curr:
if not curr.left:
res.append(curr.val)
# move to next right node
curr = curr.right
else: # has a left subtree
pre = curr.left
# find rightmost in left subtree
while pre.right:
pre = pre.right
# put cur after the pre node
pre.right = curr
# store cur node
temp = curr
# move cur to the top of the new tree
curr = curr.left
# original cur left be null, avoid infinite loops
temp.left = None
return res
``````
Last Updated: 9/21/2020, 4:44:16 PM