-
Notifications
You must be signed in to change notification settings - Fork 0
/
BinarySearchTree.py
127 lines (115 loc) · 3.63 KB
/
BinarySearchTree.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
class Node:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def __repr__(self):
return repr(self.val)
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = Node(val=val)
return
curr = self.root
while curr:
if curr.val > val:
if not curr.left:
curr.left = Node(val=val)
return
else:
curr = curr.left
if curr.val < val:
if not curr.right:
curr.right = Node(val=val)
return
else:
curr = curr.right
def find_successor(self, curr):
temp = curr
while temp.left:
temp = temp.left
return temp
def delete(self, key, curr):
if not self.root:
return self.root
if self.root.val == key and not self.root.left and not self.root.right:
self.root = None
if key < curr.val and curr.left:
curr.left = self.delete(key, curr.left)
elif key > curr.val and curr.right:
curr.right = self.delete(key, curr.right)
elif key == curr.val:
# Deleting node with one or no child
if not curr.left:
temp = curr.right
curr = None
return temp
elif not curr.right:
temp = curr.left
curr = None
return temp
# Deleting node with two child
temp = self.find_successor(curr.right)
curr.val = temp.val
curr.right = self.delete(temp.val, curr.right)
return curr
def inorder(self, curr):
ans = []
if curr:
ans = self.inorder(curr.left)
ans.append(curr.val)
ans = ans + self.inorder(curr.right)
return ans
def postorder(self, curr):
ans = []
if curr:
ans = self.postorder(curr.left)
ans = ans + self.postorder(curr.right)
ans.append(curr.val)
return ans
def preorder(self, curr):
ans = []
if curr:
ans.append(curr.val)
ans = ans + self.preorder(curr.left)
ans = ans + self.preorder(curr.right)
return ans
def search(self, key):
if self.root.val == key:
print(f'{key} found')
return
curr = self.root
while curr and curr.val != key:
if key < curr.val:
curr = curr.left
if curr:
if key == curr.val:
print(f'{key} found')
return
if key > curr.val:
curr = curr.right
if curr:
if key == curr.val:
print(f'{key} found')
return
print(f'{key} not in BST')
if __name__ == '__main__':
bst = BST()
bst.insert(50)
bst.insert(30)
bst.insert(15)
bst.insert(80)
bst.insert(75)
bst.insert(40)
print(bst.inorder(bst.root))
# print(bst.postorder(bst.root))
# print(bst.preorder(bst.root))
bst.search(75)
bst.delete(15, bst.root)
print(bst.inorder(bst.root))
bst.delete(50, bst.root)
print(bst.inorder(bst.root))
bst.delete(45, bst.root)
print(bst.inorder(bst.root))