-
Notifications
You must be signed in to change notification settings - Fork 0
/
binary_tree_traversal.py
49 lines (40 loc) · 1.18 KB
/
binary_tree_traversal.py
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
class Node:
def __init__(self, key):
self.right = None
self.left = None
self.key = key
def preorder_traversal(root, result = []):
if root:
result.append(root.key)
preorder_traversal(root.left)
preorder_traversal(root.right)
return result
def inorder_traversal(root, result = []):
if root:
inorder_traversal(root.left)
result.append(root.key)
inorder_traversal(root.right)
return result
def postorder_traversal(root, result = []):
if root:
postorder_traversal(root.left)
postorder_traversal(root.right)
result.append(root.key)
return result
def create_binary_tree():
root = Node(28)
root.left = Node(24)
root.left.right = Node(25)
root.left.left = Node(19)
root.left.left.left = Node(15)
root.left.left.right = Node(21)
root.right = Node(47)
root.right.left = Node(40)
root.right.right = Node(57)
root.right.right.left = Node(55)
root.right.right.right = Node(59)
return root
root = create_binary_tree()
assert preorder_traversal(root) == [28, 24, 19, 15, 21, 25, 47, 40, 57, 55, 59]
assert inorder_traversal(root) == [15, 19, 21, 24, 25, 28, 40, 47, 55, 57, 59]
assert postorder_traversal(root) == [15, 21, 19, 25, 24, 40, 55, 59, 57, 47, 28]