Skip to content

Commit 6c47aee

Browse files
OmkarPathakOmkarPathak
committed
Added Binary Search Tree implementation
1 parent 728e386 commit 6c47aee

1 file changed

Lines changed: 182 additions & 3 deletions

File tree

‎pygorithm/data_structures/tree.py‎

Lines changed: 182 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -51,7 +51,7 @@ def inorder(self, root):
5151
'''
5252
if root:
5353
self.inorder(root.get_left()) # traverse to leftmost child
54-
self._inorder.append(root.get_data()) # get the data of current node
54+
self._inorder.append(root.get_data()) # get the data of current node
5555
self.inorder(root.get_right()) # traverse to rightmost child
5656
return self._inorder
5757

@@ -61,7 +61,7 @@ def preorder(self, root):
6161
@type: root: Node object
6262
'''
6363
if root:
64-
self._preorder.append(root.get_data()) # get the data of current node
64+
self._preorder.append(root.get_data()) # get the data of current node
6565
self.preorder(root.get_left()) # traverse to leftmost child
6666
self.preorder(root.get_right()) # traverse to rightmost child
6767
return self._preorder
@@ -74,10 +74,189 @@ def postorder(self, root):
7474
if root:
7575
self.postorder(root.get_left()) # traverse to leftmost child
7676
self.postorder(root.get_right()) # traverse to rightmost child
77-
self._postorder.append(root.get_data()) # get the data of current node
77+
self._postorder.append(root.get_data()) # get the data of current node
7878
return self._postorder
7979

8080
# easily retrieve the source code of the BinaryTree class
8181
def get_code(self):
8282
import inspect
8383
return inspect.getsource(BinaryTree)
84+
85+
class BSTNode(object):
86+
def __init__(self, data):
87+
self.data = data
88+
self.leftChild = None
89+
self.rightChild = None
90+
self._inorder = []
91+
self._preorder = []
92+
self._postorder = []
93+
94+
# for setting left node
95+
def set_left(self, node):
96+
self.leftChild = node
97+
98+
# for setting right node
99+
def set_right(self, node):
100+
self.rightChild = node
101+
102+
# for getting the left node
103+
def get_left(self):
104+
return self.leftChild
105+
106+
# for getting right node
107+
def get_right(self):
108+
return self.rightChild
109+
110+
# for setting data of a node
111+
def set_data(self, data):
112+
self.data = data
113+
114+
# for getting data of a node
115+
def get_data(self):
116+
return self.data
117+
118+
# easily retrieve the source code of the Node class
119+
def get_code(self):
120+
import inspect
121+
return inspect.getsource(BSTNode)
122+
123+
def insert(self, data):
124+
''' For inserting the data in the Tree '''
125+
if self.data == data:
126+
return False # As BST cannot contain duplicate data
127+
128+
elif data < self.data:
129+
''' Data less than the root data is placed to the left of the root '''
130+
if self.leftChild:
131+
return self.leftChild.insert(data)
132+
else:
133+
self.leftChild = BSTNode(data)
134+
return True
135+
136+
else:
137+
''' Data greater than the root data is placed to the right of the root '''
138+
if self.rightChild:
139+
return self.rightChild.insert(data)
140+
else:
141+
self.rightChild = BSTNode(data)
142+
return True
143+
144+
def minValueBSTNode(self, BSTNode):
145+
current = BSTNode
146+
147+
# loop down to find the leftmost leaf
148+
while(current.leftChild is not None):
149+
current = current.leftChild
150+
151+
return current
152+
153+
def delete(self, data):
154+
''' For deleting the BSTNode '''
155+
if self is None:
156+
return root
157+
158+
# if current BSTNode's data is less than that of root BSTNode, then only search in left subtree else right subtree
159+
if data < self.data:
160+
self.leftChild = self.leftChild.delete(data)
161+
elif data > self.data:
162+
self.rightChild = self.rightChild.delete(data)
163+
else:
164+
# deleting BSTNode with one child
165+
if self.leftChild is None:
166+
temp = self.rightChild
167+
self = None
168+
return temp
169+
elif self.rightChild is None:
170+
temp = self.leftChild
171+
self = None
172+
return temp
173+
174+
# deleting BSTNode with two children
175+
# first get the inorder successor
176+
temp = self.minValueBSTNode(self.rightChild)
177+
self.data = temp.data
178+
self.rightChild = self.rightChild.delete(temp.data)
179+
180+
return self
181+
182+
def find(self, data):
183+
''' This function checks whether the specified data is in tree or not '''
184+
if(data == self.data):
185+
return True
186+
elif(data < self.data):
187+
if self.leftChild:
188+
return self.leftChild.find(data)
189+
else:
190+
return False
191+
else:
192+
if self.rightChild:
193+
return self.rightChild.find(data)
194+
else:
195+
return False
196+
197+
def inorder(self, root):
198+
'''
199+
@type: root: Node object
200+
'''
201+
if root:
202+
self.inorder(root.get_left()) # traverse to leftmost child
203+
self._inorder.append(root.get_data()) # get the data of current node
204+
self.inorder(root.get_right()) # traverse to rightmost child
205+
return self._inorder
206+
207+
# in this we first print the root node and then traverse towards leftmost node and then to the rightmost node
208+
def preorder(self, root):
209+
'''
210+
@type: root: Node object
211+
'''
212+
if root:
213+
self._preorder.append(root.get_data()) # get the data of current node
214+
self.preorder(root.get_left()) # traverse to leftmost child
215+
self.preorder(root.get_right()) # traverse to rightmost child
216+
return self._preorder
217+
218+
# in this we first traverse to the leftmost node and then to the rightmost node and then print the data
219+
def postorder(self, root):
220+
'''
221+
@type: root: Node object
222+
'''
223+
if root:
224+
self.postorder(root.get_left()) # traverse to leftmost child
225+
self.postorder(root.get_right()) # traverse to rightmost child
226+
self._postorder.append(root.get_data()) # get the data of current node
227+
return self._postorder
228+
229+
class BinarySearchTree(object):
230+
def __init__(self):
231+
self.root = None
232+
233+
def insert(self, data):
234+
if self.root:
235+
return self.root.insert(data)
236+
else:
237+
self.root = BSTNode(data)
238+
return True
239+
240+
def delete(self, data):
241+
if self.root is not None:
242+
return self.root.delete(data)
243+
244+
def find(self, data):
245+
if self.root:
246+
return self.root.find(data)
247+
else:
248+
return False
249+
250+
def preorder(self):
251+
if self.root is not None:
252+
return self.root.preorder(self.root)
253+
254+
def inorder(self):
255+
print()
256+
if self.root is not None:
257+
return self.root.inorder(self.root)
258+
259+
def postorder(self):
260+
print()
261+
if self.root is not None:
262+
return self.root.postorder(self.root)

0 commit comments

Comments
 (0)