Binary Tree Preorder Traversal
franklinqin0 StackTreeMorris
# 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
2
3
4
5
# Solution
Let be the number of nodes in the tree.
# Recursion
Complexity
time:
space:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def preorder(node: TreeNode):
if not node: return
res.append(node.val)
preorder(node.left)
preorder(node.right)
preorder(root)
return res
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# Follow Up
Recursive solution is trivial, could you do it iteratively?
# Iteration
Complexity
time:
space:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = [root]
while stack:
curr = stack.pop()
if curr:
res.append(curr.val)
stack.append(curr.right)
stack.append(curr.left)
return res
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# Morris Traversal
Complexity
time:
space:
def preorderTraversal(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:
res.append(root.val)
# `pre.right` points to root
pre.right = root
# traverse left subtree
root = root.left
else: # left subtree is done traversing
# 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24