-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBST.py
110 lines (91 loc) · 3.67 KB
/
BST.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
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
class Node:
def __init__(self, input_value):
self.left = None
self.right = None
self.value = input_value
class BST:
def __init__(self, root_value):
self.root = Node(root_value)
def insert(self, input_value):
self.root = self.insert_recurse(self.root, input_value)
def insert_recurse(self, input_node, input_value):
if input_node is None:
input_node = Node(input_value)
else:
if input_value < input_node.value:
input_node.left = self.insert_recurse(
input_node.left, input_value)
elif input_value > input_node.value:
input_node.right = self.insert_recurse(
input_node.right, input_value)
else:
raise ValueError("Duplicate Value")
return input_node
def __contains__(self, input_value):
return self._contains_recurse(self.root, input_value)
def _contains_recurse(self, input_node, input_value):
if input_node is None:
return False
elif input_node.value == input_value:
return True
elif input_value < input_node.value:
return self._contains_recurse(input_node.left, input_value)
elif input_value > input_node.value:
return self._contains_recurse(input_node.right, input_value)
def delete(self, input_value):
# TODO: Delete value from tree
pass
def find_min(self):
current_node = self.root
while current_node.left is not None:
current_node = current_node.left
return current_node.value
def find_max(self):
current_node = self.root
while current_node.right is not None:
current_node = current_node.right
return current_node.value
def print_inorder(self):
output_array = []
output_array = self._print_inorder_recurse(self.root, output_array)
print(output_array)
def _print_inorder_recurse(self, input_node, input_array):
if input_node is not None:
input_array = self._print_inorder_recurse(
input_node.left, input_array)
input_array.append(input_node.value)
input_array = self._print_inorder_recurse(
input_node.right, input_array)
return input_array
def print_preorder(self):
output_array = []
output_array = self._print_preorder_recurse(self.root, output_array)
print(output_array)
def _print_preorder_recurse(self, input_node, input_array):
if input_node is not None:
input_array.append(input_node.value)
input_array = self._print_preorder_recurse(
input_node.left, input_array)
input_array = self._print_preorder_recurse(
input_node.right, input_array)
return input_array
def print_postorder(self):
output_array = []
output_array = self._print_postorder_recurse(self.root, output_array)
print(output_array)
def _print_postorder_recurse(self, input_node, input_array):
if input_node is not None:
input_array = self._print_postorder_recurse(
input_node.left, input_array)
input_array = self._print_postorder_recurse(
input_node.right, input_array)
input_array.append(input_node.value)
return input_array
if __name__ == "__main__":
binary_search_tree = BST(50)
binary_search_tree.insert(70)
binary_search_tree.insert(10)
binary_search_tree.insert(20)
binary_search_tree.insert(30)
binary_search_tree.insert(5)
binary_search_tree.print_inorder()