/
binarytree.py
399 lines (349 loc) · 18 KB
/
binarytree.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
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
#!python
class BinaryTreeNode(object):
def __init__(self, data):
"""Initialize this binary tree node with the given data."""
self.data = data
self.left = None
self.right = None
def __repr__(self):
"""Return a string representation of this binary tree node."""
return 'BinaryTreeNode({!r})'.format(self.data)
def is_leaf(self):
"""Return True if this node is a leaf (has no children)."""
# Check if both left child and right child have no value
return self.left is None and self.right is None
def is_branch(self):
"""Return True if this node is a branch (has at least one child)."""
# Check if either left child or right child has a value
return self.left is not None or self.right is not None
def height(self):
"""Return the height of this node (the number of edges on the longest
downward path from this node to a descendant leaf node).
Best and worst case running time: O(n) to traverse every edge in the tree to find longest path"""
# Check if left or right child has a value and if so calculate its height
if self.is_leaf():
return 0
left_height = 0
right_height = 0
if self.left:
left_height += self.left.height()
if self.right:
right_height += self.right.height()
# Return one more than the greater of the left height and right height
return max(left_height, right_height) + 1
class BinarySearchTree(object):
def __init__(self, items=None):
"""Initialize this binary search tree and insert the given items."""
self.root = None
self.size = 0
if items is not None:
for item in items:
self.insert(item)
def __repr__(self):
"""Return a string representation of this binary search tree."""
return 'BinarySearchTree({} nodes)'.format(self.size)
def is_empty(self):
"""Return True if this binary search tree is empty (has no nodes)."""
return self.root is None
def height(self):
"""Return the height of this tree (the number of edges on the longest
downward path from this tree's root node to a descendant leaf node).
Best and worst case running time: O(n) to traverse every edge in the tree to find longest path"""
# Check if root node has a value and if so calculate its height
return self.root.height()
def contains(self, item):
"""Return True if this binary search tree contains the given item.
Best case running time: O(1) if the item being looked for is the root
Worst case running time: O(log[base2]n) each time a search is done, results are divided in half"""
# Find a node with the given item, if any
# node = self._find_node_iterative(item)
node = self._find_node_recursive(item, self.root)
# Return True if a node was found, or False
return node is not None
def search(self, item):
"""Return an item in this binary search tree matching the given item,
or None if the given item is not found.
Best case running time: O(1) if the item being looked for is the root
Worst case running time: O(log[base2]n) each time a search is done, results are divided in half"""
# Find a node with the given item, if any
# node = self._find_node_iterative(item)
node = self._find_node_recursive(item, self.root)
# Return the node's data if found, or None
return node.data if node else None
def insert(self, item):
"""Insert the given item in order into this binary search tree.
Best case running time: O(1) if the item being looked for is the root
Worst case running time: O(log[base2]n) each time a search is done, results are divided in half"""
new_node = BinaryTreeNode(item)
# Handle the case where the tree is empty
if self.is_empty():
# Create a new root node
self.root = new_node
# Increase the tree size
self.size += 1
return
# Find the parent node of where the given item should be inserted
# parent = self._find_parent_node_iterative(item)
parent = self._find_parent_node_recursive(item, self.root)
# Check if the given item should be inserted left of parent node
if parent.data > item:
# Create a new node and set the parent's left child
parent.left = new_node
# Check if the given item should be inserted right of parent node
elif parent.data < item:
# Create a new node and set the parent's right child
parent.right = new_node
# Increase the tree size
self.size += 1
def _find_node_iterative(self, item):
"""Return the node containing the given item in this binary search tree,
or None if the given item is not found. Search is performed iteratively
starting from the root node.
Best case running time: O(1) if the item being looked for is the root
Worst case running time: O(log[base2]n) each time a search is done, results are divided in half"""
# Start with the root node
node = self.root
# Loop until we descend past the closest leaf node
while node is not None:
# Check if the given item matches the node's data
if item == node.data:
# Return the found node
return node
# Check if the given item is less than the node's data
elif item < node.data:
# Descend to the node's left child
node = node.left
# Check if the given item is greater than the node's data
elif item > node.data:
# Descend to the node's right child
node = node.right
# Not found
return None
def _find_node_recursive(self, item, node):
"""Return the node containing the given item in this binary search tree,
or None if the given item is not found. Search is performed recursively
starting from the given node (give the root node to start recursion).
Best case running time: O(1) if the item being looked for is the root
Worst case running time: O(log[base2]n) each time a search is done, results are divided in half"""
# Check if starting node exists
if node is None:
# Not found (base case)
return None
# Check if the given item matches the node's data
elif item == node.data:
# Return the found node
return node
# Check if the given item is less than the node's data
elif item < node.data:
# Recursively descend to the node's left child, if it exists
return self._find_node_recursive(item, node.left)
# Check if the given item is greater than the node's data
elif item > node.data:
# Recursively descend to the node's right child, if it exists
return self._find_node_recursive(item, node.right)
def _find_parent_node_iterative(self, item):
"""Return the parent node of the node containing the given item
(or the parent node of where the given item would be if inserted)
in this tree, or None if this tree is empty or has only a root node.
Search is performed iteratively starting from the root node.
Best case running time: O(1) if the item being looked for is the root
Worst case running time: O(log[base2]n) each time a search is done, results are divided in half"""
# Start with the root node and keep track of its parent
node = self.root
parent = None
# Loop until we descend past the closest leaf node
while node is not None:
# Check if the given item matches the node's data
if item == node.data:
# Return the parent of the found node
return parent
# Check if the given item is less than the node's data
elif item < node.data:
# Update the parent and descend to the node's left child
parent = node
node = node.left
# Check if the given item is greater than the node's data
elif item > node.data:
# Update the parent and descend to the node's right child
parent = node
node = node.right
# Not found
return parent
def _find_parent_node_recursive(self, item, node, parent=None):
"""Return the parent node of the node containing the given item
(or the parent node of where the given item would be if inserted)
in this tree, or None if this tree is empty or has only a root node.
Search is performed recursively starting from the given node
(give the root node to start recursion)."""
# Check if starting node exists
if node is None:
# Not found (base case)
return parent
# Check if the given item matches the node's data
if item == node.data:
# Return the parent of the found node
return parent
# Check if the given item is less than the node's data
elif item < node.data:
# Recursively descend to the node's left child, if it exists
return self._find_parent_node_recursive(item, node.left, node) # Hint: Remember to update the parent parameter
# Check if the given item is greater than the node's data
elif item > node.data:
# Recursively descend to the node's right child, if it exists
return self._find_parent_node_recursive(item, node.right, node) # Hint: Remember to update the parent parameter
# def delete(self, item):
# """Remove given item from this tree, if present, or raise ValueError.
# TODO: Best case running time: ??? under what conditions?
# TODO: Worst case running time: ??? under what conditions?"""
# # TODO: Use helper methods and break this algorithm down into 3 cases
# # based on how many children the node containing the given item has and
# # implement new helper methods for subtasks of the more complex cases
# # PSEUDO BRAINSTORM
def items_in_order(self):
"""Return an in-order list of all items in this binary search tree."""
items = []
if not self.is_empty():
# Traverse tree in-order from root, appending each node's item
# items.append uncalled function that you can later call
self._traverse_in_order_recursive(self.root, items.append)
# Return in-order list of all items in tree
return items
def _traverse_in_order_recursive(self, node, visit):
"""Traverse this binary tree with recursive in-order traversal (DFS).
Start at the given node and visit each node with the given function.
Running time: O(n) visit function goes through every node
Memory usage: depends on height - O(log[base2]n) best case | O(n) if unbalanced tree"""
# Traverse left subtree, if it exists
if node.left:
self._traverse_in_order_recursive(node.left, visit)
# Visit this node's data with given function
# Note: visit is a built in python function
# https://docs.python.org/3/library/ast.html#ast.NodeVisitor
visit(node.data)
# Traverse right subtree, if it exists
if node.right:
self._traverse_in_order_recursive(node.right, visit)
# def _traverse_in_order_iterative(self, node, visit):
# """Traverse this binary tree with iterative in-order traversal (DFS).
# Start at the given node and visit each node with the given function.
# TODO: Running time: ??? Why and under what conditions?
# TODO: Memory usage: ??? Why and under what conditions?"""
# # TODO: Traverse in-order without using recursion (stretch challenge)
def items_pre_order(self):
"""Return a pre-order list of all items in this binary search tree."""
items = []
if not self.is_empty():
# Traverse tree pre-order from root, appending each node's item
self._traverse_pre_order_recursive(self.root, items.append)
# Return pre-order list of all items in tree
return items
def _traverse_pre_order_recursive(self, node, visit):
"""Traverse this binary tree with recursive pre-order traversal (DFS).
Start at the given node and visit each node with the given function.
Running time: O(n) visit function goes through every node
Memory usage: depends on height - O(log[base2]n) best case | O(n) if unbalanced tree"""
# Visit this node's data with given function
# Note: visit is a built in python function
# https://docs.python.org/3/library/ast.html#ast.NodeVisitor
visit(node.data)
# Traverse left subtree, if it exists
if node.left:
self._traverse_pre_order_recursive(node.left, visit)
# Traverse right subtree, if it exists
if node.right:
self._traverse_pre_order_recursive(node.right, visit)
# def _traverse_pre_order_iterative(self, node, visit):
# """Traverse this binary tree with iterative pre-order traversal (DFS).
# Start at the given node and visit each node with the given function.
# TODO: Running time: ??? Why and under what conditions?
# TODO: Memory usage: ??? Why and under what conditions?"""
# # TODO: Traverse pre-order without using recursion (stretch challenge)
def items_post_order(self):
"""Return a post-order list of all items in this binary search tree."""
items = []
if not self.is_empty():
# Traverse tree post-order from root, appending each node's item
self._traverse_post_order_recursive(self.root, items.append)
# Return post-order list of all items in tree
return items
def _traverse_post_order_recursive(self, node, visit):
"""Traverse this binary tree with recursive post-order traversal (DFS).
Start at the given node and visit each node with the given function.
Running time: O(n) visit function goes through every node
Memory usage: depends on height - O(log[base2]n) best case | O(n) if unbalanced tree"""
# Traverse left subtree, if it exists
if node.left:
self._traverse_post_order_recursive(node.left, visit)
# Traverse right subtree, if it exists
if node.right:
self._traverse_post_order_recursive(node.right, visit)
# Visit this node's data with given function
# Note: visit is a built in python function
# https://docs.python.org/3/library/ast.html#ast.NodeVisitor
visit(node.data)
# def _traverse_post_order_iterative(self, node, visit):
# """Traverse this binary tree with iterative post-order traversal (DFS).
# Start at the given node and visit each node with the given function.
# TODO: Running time: ??? Why and under what conditions?
# TODO: Memory usage: ??? Why and under what conditions?"""
# # TODO: Traverse post-order without using recursion (stretch challenge)
def items_level_order(self):
"""Return a level-order list of all items in this binary search tree."""
items = []
if not self.is_empty():
# Traverse tree level-order from root, appending each node's item
self._traverse_level_order_iterative(self.root, items.append)
# Return level-order list of all items in tree
return items
def _traverse_level_order_iterative(self, start_node, visit):
"""Traverse this binary tree with iterative level-order traversal (BFS).
Start at the given node and visit each node with the given function.
Running time: O(n) iterates through all nodes
Memory usage: O(n) or 2^(h + 1) - 1 or 2^(log[base2]n). Height is logarithmic to number of nodes. However, 2 and logbase2 cancel out so left with n"""
from queue import LinkedQueue
# Create queue to store nodes not yet traversed in level-order
queue = LinkedQueue()
# Enqueue given starting node
queue.enqueue(start_node)
# Loop until queue is empty
while queue.is_empty() == False:
# Dequeue node at front of queue
node = queue.dequeue()
# Visit this node's data with given function
# Note: visit is a built in python function
# https://docs.python.org/3/library/ast.html#ast.NodeVisitor
visit(node.data)
# Enqueue this node's left child, if it exists
if node.left:
queue.enqueue(node.left)
# Enqueue this node's right child, if it exists
if node.right:
queue.enqueue(node.right)
def test_binary_search_tree():
# Create a complete binary search tree of 3, 7, or 15 items in level-order
# items = [2, 1, 3]
items = [4, 2, 6, 1, 3, 5, 7]
# items = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]
print('items: {}'.format(items))
tree = BinarySearchTree()
print('tree: {}'.format(tree))
print('root: {}'.format(tree.root))
print('\nInserting items:')
for item in items:
tree.insert(item)
print('insert({}), size: {}'.format(item, tree.size))
print('root: {}'.format(tree.root))
print('\nSearching for items:')
for item in items:
result = tree.search(item)
print('search({}): {}'.format(item, result))
item = 123
result = tree.search(item)
print('search({}): {}'.format(item, result))
print('\nTraversing items:')
print('items in-order: {}'.format(tree.items_in_order()))
print('items pre-order: {}'.format(tree.items_pre_order()))
print('items post-order: {}'.format(tree.items_post_order()))
print('items level-order: {}'.format(tree.items_level_order()))
if __name__ == '__main__':
test_binary_search_tree()