# Binary Tree Preorder Traversal

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

## # Solution

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

### # Recursion

Complexity

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

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

Recursive solution is trivial, could you do it iteratively?

### # Iteration

Complexity

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

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

### # Morris Traversal

Complexity

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

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