-
Notifications
You must be signed in to change notification settings - Fork 0
/
binary_search_tree.py
57 lines (43 loc) · 1.61 KB
/
binary_search_tree.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
class Node:
def __init__(self, data=None):
self.data = data
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def _insert_recursive(self, data, node):
if data["id"] < node.data["id"]:
if node.left is None:
node.left = Node(data)
else:
self._insert_recursive(data, node.left)
elif data["id"] > node.data["id"]:
if node.right is None:
node.right = Node(data)
else:
self._insert_recursive(data, node.right)
else:
return
def insert(self, data):
if self.root is None:
self.root = Node(data)
else:
self._insert_recursive(data, self.root)
def _search_recursive(self, blog_post_id, node):
if blog_post_id == node.data["id"]:
return node.data
if blog_post_id < node.data["id"] and node.left is not None:
if blog_post_id == node.left.data["id"]:
return node.left.data
return self._search_recursive(blog_post_id, node.left)
if blog_post_id > node.data["id"] and node.right is not None:
if blog_post_id == node.right.data["id"]:
return node.right.data
return self._search_recursive(blog_post_id, node.right)
return False
def search(self, blog_post_id):
blog_post_id = int(blog_post_id)
if self.root is None:
return False
return self._search_recursive(blog_post_id, self.root)