Repository navigation
Expand file tree
/
Copy pathpreorder_traversal.py
More file actions
77 lines (59 loc) · 1.94 KB
/
Copy pathpreorder_traversal.py
File metadata and controls
77 lines (59 loc) · 1.94 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
r"""Pre-order Traversal.
Pre-order traversal is to visit the root first. Then traverse the left subtree. Finally, traverse the right
subtree.
Example:
```text
1
/ \
2 3
/ \
4 5
```
Output: `[1, 2, 4, 5, 3]`
"""
from src.binary_tree.tree_node import TreeNode
def preorder_traversal_iterative(root: TreeNode) -> list[int]:
"""Traverse iteratively with an explicit stack. Time: O(N), Space: O(N)."""
output = []
if root is None:
return output
stack = [root]
while stack:
root_node = stack.pop()
if root_node is not None:
output.append(root_node.val)
if root_node.right is not None:
stack.append(root_node.right)
if root_node.left is not None:
stack.append(root_node.left)
return output
def preorder_traversal_morris(root: TreeNode) -> list[int]:
"""Traverse using threaded links through predecessors, avoiding a stack. Time: O(N), Space: O(1)."""
node, output = root, []
while node:
if not node.left:
output.append(node.val)
node = node.right
else:
predecessor = node.left
while predecessor.right and predecessor.right is not node:
predecessor = predecessor.right
if not predecessor.right:
output.append(node.val)
predecessor.right = node
node = node.left
else:
predecessor.right = None
node = node.right
return output
def preorder_traversal_recursive(root: TreeNode) -> list[int]:
"""Recursively visit the node, then traverse left, then traverse right. Time: O(N), Space: O(N)."""
values = []
if not root:
return values
values.append(root.val)
if root.left:
values.extend(preorder_traversal_recursive(root.left))
if root.right:
values.extend(preorder_traversal_recursive(root.right))
return values