Binary Tree Inorder Traversal

Hash TableStackTreeMorris

# 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

1
2
3
4
5

# Solution

Let $n$ be the number of nodes in the tree.

# Recursion

Complexity

time: $O(n)$
space: $O(n)$

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

inorder(root)
return res

1
2
3
4
5
6
7
8
9
10

or even simpler:

def inorderTraversal(self, root: TreeNode) -> List[int]:
def inorder(root: TreeNode):
return inorder(root.left) + [root.val] + inorder(root.right) if root else []

return inorder(root)

1
2
3
4
5

Recursive solution is trivial, could you do it iteratively?

# Iteration

Complexity

time: $O(n)$
space: $O(n)$

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# Morris Traversal

Complexity

time: $O(n)$
space: $O(1)$

def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
pre = None

while root:
if root.left:
pre = root.left
while pre.right and pre.right != root:
pre = pre.right

if not pre.right:
# pre.right points to root
pre.right = root
# traverse left subtree
root = root.left
else: # left subtree is done traversing
res.append(root.val)
# cut connection
pre.right = None
root = root.right
else:
res.append(root.val)
root = root.right
return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24