Skip to content
Navigation Menu
{{ message }}
forked from geekcomputers/Python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary_search_tree.py
More file actions
executable file
·371 lines (342 loc) · 11 KB
/
Copy pathbinary_search_tree.py
File metadata and controls
executable file
·371 lines (342 loc) · 11 KB
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
import sys
class Node:
"""Class for node of a tree"""
def __init__(self, info):
"""Initialising a node"""
self.info = info
self.left = None
self.right = None
# self.level = None
def __str__(self):
return str(self.info)
def __del__(self):
del self
class BinarySearchTree:
"""Class for BST"""
def __init__(self):
"""Initialising a BST"""
self.root = None
def insert(self, val):
"""Creating a BST with root value as val"""
# Check if tree has root with None value
if self.root is None:
self.root = Node(val)
# Here the tree already has one root
else:
current = self.root
while True:
if val < current.info:
if current.left:
current = current.left
else:
current.left = Node(val)
break
elif val > current.info:
if current.right:
current = current.right
else:
current.right = Node(val)
break
else:
break
def search(self, val, to_delete = False):
current = self.root
prev = -1
while current:
if val < current.info:
prev = current
current = current.left
elif val > current.info:
prev = current
current = current.right
elif current.info == val:
if not to_delete:
return 'Match Found'
return prev
else:
break
if not to_delete:
return 'Not Found'
# Method to delete a tree-node if it exists, else error message will be returned.
def delete(self, val):
prev = self.search(val, True)
# Check if node exists
if prev is not None:
# Check if node is the Root node
if prev == -1:
temp = self.root.left
prev2 = None
while temp.right:
prev2 = temp
temp = temp.right
if prev2 is None:
self.root.left = temp.left
self.root.info = temp.info
else:
prev2.right = None
self.root.info = temp.info
print('Deleted Root ', val)
# Check if node is to left of its parent
elif prev.left and prev.left.info == val:
# Check if node is leaf node
if prev.left.left is prev.left.right:
prev.left = None
print('Deleted Node ', val)
# Check if node has child at left and None at right
elif prev.left.left and prev.left.right is None:
prev.left = prev.left.left
print('Deleted Node ', val)
# Check if node has child at right and None at left
elif prev.left.left is None and prev.left.right:
prev.left = prev.left.right
print('Deleted Node ', val)
# Here node to be deleted has 2 children
elif prev.left.left and prev.left.right:
temp = prev.left
while temp.right is not None:
prev2 = temp
temp = temp.right
prev2.right = None
prev.left.info = temp.info
print('Deleted Node ', val)
else:
print('Error Left')
# Check if node is to right of its parent
elif prev.right.info == val:
flag = 0
# Check is node is a leaf node
if prev.right.left is prev.right.right:
prev.right = None
flag = 1
print('Deleted Node ', val)
# Check if node has left child at None at right
if prev.right and prev.right.left and prev.right.right is None:
prev.right = prev.right.left
print('Deleted Node ', val)
# Check if node has right child at None at left
elif prev.right and prev.right.left is None and prev.right.right:
prev.right = prev.right.right
print('Deleted Node ', val)
elif prev.right and prev.right.left and prev.right.right:
temp = prev.right
while temp.left is not None:
prev2 = temp
temp = temp.left
prev2.left = None
prev.right.info = temp.info
print('Deleted Node ', val)
else:
if flag == 0:
print("Error")
else:
print("Node doesn't exists")
def __str__(self):
return 'Not able to print tree yet'
def is_bst(node, lower_lim=None, upper_lim=None):
"""Function to find is a binary tree is a binary search tree."""
if lower_lim is not None and node.info < lower_lim:
return False
if upper_lim is not None and node.info > upper_lim:
return False
is_left_bst = True
is_right_bst = True
if node.left is not None:
is_left_bst = is_bst(node.left, lower_lim, node.info)
if is_left_bst and node.right is not None:
is_right_bst = is_bst(node.right, node.info, upper_lim)
return is_left_bst and is_right_bst
def postorder(node):
# L R N : Left , Right, Node
if node is None:
return
if node.left:
postorder(node.left)
if node.right:
postorder(node.right)
print(node.info)
def inorder(node):
# L N R : Left, Node , Right
if node is None:
return
if node.left:
inorder(node.left)
print(node.info)
if node.right:
inorder(node.right)
def preorder(node):
# N L R : Node , Left, Right
if node is None:
return
print(node.info)
if node.left:
preorder(node.left)
if node.right:
preorder(node.right)
# Levelwise
def bfs(node):
queue = []
if node:
queue.append(node)
while queue != []:
temp = queue.pop(0)
print(temp.info)
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)
def preorder_itr(node):
# N L R : Node, Left , Right
stack = [node]
values = []
while stack != []:
temp = stack.pop()
print(temp.info)
values.append(temp.info)
if temp.right:
stack.append(temp.right)
if temp.left:
stack.append(temp.left)
return values
def inorder_itr(node):
# L N R : Left, Node, Right
# 1) Create an empty stack S.
# 2) Initialize current node as root
# 3) Push the current node to S and set current = current->left until current is NULL
# 4) If current is NULL and stack is not empty then
# a) Pop the top item from stack.
# b) Print the popped item, set current = popped_item->right
# c) Go to step 3.
# 5) If current is NULL and stack is empty then we are done.
stack = []
current = node
while True:
if current != None:
stack.append(current) # L
current = current.left
elif stack != []:
temp = stack.pop()
print(temp.info) # N
current = temp.right # R
else:
break
def postorder_itr(node):
# L R N
# 1. Push root to first stack.
# 2. Loop while first stack is not empty
# 2.1 Pop a node from first stack and push it to second stack
# 2.2 Push left and right children of the popped node to first stack
# 3. Print contents of second stack
s1, s2 = [node], []
while s1 != []:
temp = s1.pop()
s2.append(temp)
if temp.left:
s1.append(temp.left)
if temp.right:
s1.append(temp.right)
print(*(s2[::-1]))
def bst_frm_pre(pre_list):
box = Node(pre_list[0])
if len(pre_list) > 1:
if len(pre_list) == 2:
if pre_list[1] > pre_list[0]:
box.right = Node(pre_list[1])
else:
box.left = Node(pre_list[1])
else:
all_less = False
for i in range(1, len(pre_list)):
if pre_list[i] > pre_list[0]:
break
else:
all_less = True
if i != 1:
box.left = bst_frm_pre(pre_list[1 : i])
if not all_less:
box.right = bst_frm_pre(pre_list[i:])
return box
# Function to find the lowest common ancestor of nodes with values c1 and c2.
# It return value in the lowest common ancestor, -1 indicates value returned for None.
# Note that both values v1 and v2 should be present in the bst.
def lca(t_node, c1, c2):
if c1 == c2:
return c1
current = t_node
while current:
if c1 < current.info and c2 < current.info:
current = current.left
elif c1 > current.info and c2 > current.info:
current = current.right
else:
return current.info
return -1
# Function to print element vertically which lie just below the root node
def vertical_middle_level(t_node):
e = (t_node, 0) # 0 indicates level 0, to left we have -ve and to right +ve
queue = [e]
ans = []
# Do a level-order traversal and assign level-value to each node
while queue != []:
temp, level = queue.pop(0)
if level == 0:
ans.append(str(temp.info))
if temp.left:
queue.append((temp.left, level - 1))
if temp.right:
queue.append((temp.right, level + 1))
return ' '.join(ans)
def get_level(n, val):
c_level = 0
while n.info != val:
if val < n.info:
n = n.left
elif val > n.info:
n = n.right
c_level += 1
if n is None:
return -1
return c_level
def depth(node):
if node is None:
return 0
l_depth, r_depth = 0, 0
if node.left:
l_depth = depth(node.left)
if node.right:
r_depth = depth(node.right)
# print(node.info, l_depth, r_depth)
return 1 + max(l_depth, r_depth)
t = BinarySearchTree()
t.insert(10)
t.insert(5)
t.insert(15)
t.insert(3)
t.insert(1)
t.insert(0)
t.insert(2)
t.insert(7)
t.insert(12)
t.insert(18)
t.insert(19)
print(depth(t.root))
# inorder(t.root)
# print()
# print(t.search(5))
# t.delete(7)
# t.delete(5)
# t.delete(3)
# t.delete(15)
# inorder(t.root)
# print()
# t.delete(2)
# t.delete(3)
# t.delete(7)
# t.delete(19)
# t.delete(1)
# inorder(t.root)
# b = BinarySearchTree()
# b.root = bst_frm_pre(preorder_itr(t.root))
# print(preorder_itr(b.root) == preorder_itr(t.root))
# print(lca(t.root, 3, 18))
# print(vertical_middle_level(t.root))
# print(get_level(t.root, 1))
You can’t perform that action at this time.