-
Notifications
You must be signed in to change notification settings - Fork 0
/
question_1_d.py
217 lines (179 loc) · 7.77 KB
/
question_1_d.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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
# Project 1 Question 1-d - Python
# Created by Ryan Doherty
# (8 points) (You must submit code for this question! ) Submit an implementation
# of the following iterative methods in a Binary Search Tree. You do not need to
# submit written answers to the framework from above, but it might be useful for
# you to consider the answers to those questions when writing code. Note that the
# Iter suffix simply means that the function is iterative. Keep in mind that an
# iterative solution cannot make a single recursive call!
# 1. insertIter
# 2. deleteIter
# 3. findNextIter
# 4. findPrevIter
# 5. findMinIter
# 6. findMaxIter
class Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
self.traversals = 0
# Inserts a value into the BST Iterively:
def insertIter(self, val):
inserted = False
curr = self
if curr.val:
while not inserted:
if val < curr.val:
if curr.left is None:
curr.left = Node(val)
inserted = True
else:
self.traversals += 1 # Add to traversals
curr = curr.left
elif val > curr.val:
if curr.right is None:
curr.right = Node(val)
inserted = True
else:
self.traversals += 1 # Add to traversals
curr = curr.right
else:
self.val = val
# Deletes a value in the BST Iterively:
def deleteIter(self, val):
curr = self
parent = self
print("Deleting:", val)
while val:
# Base:
if curr is None:
print(val, "not found.")
return self
# Search for the value:
elif val < curr.val:
parent = curr
self.traversals += 1 # Add to traversals
curr = curr.left # Move left
elif val > curr.val:
parent = curr
self.traversals += 1 # Add to traversals
curr = curr.right # Move right
else: # Delete the current node
# If a leaf:
if curr.left is None and curr.right is None:
# Delete it
if parent.left is curr: # If curr is left child:
parent.left = None
elif parent.right is curr: # If curr is right child:
parent.right = None
return self
# If only one child:
elif curr.left is None or curr.right is None:
if parent.left is curr: # If current is a left child:
if curr.left:
parent.left = curr.left # Parent's left becomes current's left.
curr = None
elif curr.right:
parent.left = curr.right # Parent's left becomes current's right.
curr = None
elif parent.right is curr: # If current is a right child:
if curr.left:
parent.right = curr.left # Parent's right becomes current's left.
elif curr.right:
parent.right = curr.right # Parent's right becomes current's right.
return self
# If two children:
else:
if self.findNextIter(curr.val):
temp = self.findNextIter(curr.val) # Find the sucessor.
if temp.val < curr.val:
curr.val = temp.val # Set the current node's value to the sucessor.
parent = curr
self.traversals += 1 # Add to traversals
curr = curr.left # Move left
elif temp.val > curr.val:
curr.val = temp.val # Set the current node's value to the sucessor.
parent = curr
self.traversals += 1 # Add to traversals
curr = curr.right # Move right
val = temp.val # Continues the delete with the sucessor as the new target.
else:
# curr = None
if parent.left is curr: # If current is a left child:
parent.left = None
elif parent.right is curr: # If current is a right child:
parent.right = None
return
# Finds the next biggest element in the BST Iterively:
def findNextIter(self, start):
curr = self
while True:
if curr is None:
return curr
elif curr.val + 1 is start: # If curr is only one larger it must be the next biggest element.
return curr
elif curr.val <= start: # If value is less, go right
self.traversals += 1 # Add to traversals
curr = curr.right
elif curr.val > start: # If value is greater, go left
if curr.left:
self.traversals += 1 # Add to traversals
curr = curr.left
else:
return curr
# Finds the next smallest element in the BST Iterively:
def findPrevIter(self, start):
curr = self
while True:
if curr is None:
return curr
elif curr.val - 1 is start: # If curr is only one larger it must be the next biggest element.
return curr
elif curr.val < start: # If value is less, go right
if curr.right:
self.traversals += 1 # Add to traversals
curr = curr.right
else:
return curr
elif curr.val >= start: # If value is greater, go left
self.traversals += 1 # Add to traversals
curr = curr.left
# Finds the minimum value in the BST Iterively:
def findMinIter(self):
curr = self
while True:
if curr.left is None:
return curr
else:
self.traversals += 1 # Add to traversals
curr = curr.left
# Finds the maximum value in the BST Iterively:
def findMaxIter(self):
curr = self
while True:
if curr.right is None:
return curr
else:
self.traversals += 1 # Add to traversals
curr = curr.right
# Prints the BST In-Order:
def printTree(self):
if self.left:
self.left.printTree()
print(self.val, end=' ')
if self.right:
self.right.printTree()
if __name__ == "__main__":
root = Node(None)
arr_in = [5, 4, 12, 2, 0, 9, 22, 8, 11]
for n in arr_in:
root.insertIter(n) # 1. insertIter
root.printTree()
print()
print("Min value is:", root.findMinIter().val) # 5. findMinIter
print("Max value is:", root.findMaxIter().val) # 6. findMaxIter
print("Next node is:", root.findNextIter(5).val) # 3. findNextIter
print("Previous node is:", root.findPrevIter(9).val) # 4. findPrevIter
root.deleteIter(4) # 2. deleteIter
root.printTree()