I am trying to implement a Binary Search Tree and I believe my logic for the insert method is perfectly fine but my code throws a 'maximum recursion depth exceeded in comparison' error when I run it.
Update: I edited my code to fix maximum recursion depth but now I am getting a different AttributeError.
The following is my updated code:
class BSTNode:
def __init__(self, key, value=None):
self.key = key
self.value = value
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
self.size = 0
def insert(self, key, value):
if self.root is None:
self.root = BSTNode(key, value)
elif key < self.root.key:
if self.root.left is None:
self.root.left = BSTNode(key, value)
else:
self.root.left.insert(key, value)
elif key > self.root.key:
if self.root.right is None:
self.root.right = BSTNode(key, value)
else:
self.root.right.insert(key, value)
return self.root
if __name__ == '__main__':
T = BST()
T.insert(5, 'Mujeeb')
T.insert(4, 'Hamza')
T.insert(7, 'Ayesha')
T.insert(9, 'Mahnoor')
T.insert(11, 'Ali')
print(T.root.right.key)
The error I was getting:
---------------------------------------------------------------------------
RecursionError Traceback (most recent call last)
<ipython-input-29-1eef6d5c8be5> in <module>
23 T = BST()
24 T.insert(5, 'Mujeeb')
---> 25 T.insert(4, 'Hamza')
26 T.insert(7, 'Ayesha')
27
<ipython-input-29-1eef6d5c8be5> in insert(self, key, value)
15 self.root = BSTNode(key, value)
16 elif key < self.root.key:
---> 17 self.root.left = self.insert(key, value)
18 elif key > self.root.key:
19 self.root.right = self.insert(key, value)
... last 1 frames repeated, from the frame below ...
<ipython-input-29-1eef6d5c8be5> in insert(self, key, value)
15 self.root = BSTNode(key, value)
16 elif key < self.root.key:
---> 17 self.root.left = self.insert(key, value)
18 elif key > self.root.key:
19 self.root.right = self.insert(key, value)
RecursionError: maximum recursion depth exceeded in comparison
The new error I get with the updated code:
AttributeError Traceback (most recent call last)
<ipython-input-23-8ebfd3bbaceb> in <module>
30 if __name__ == '__main__':
31 T = BST()
---> 32 T.insert(5, 'Mujeeb')
33 T.insert(4, 'Hamza')
34 T.insert(7, 'Ayesha')
<ipython-input-23-8ebfd3bbaceb> in insert(self, key, value)
14 if self.root is None:
15 self.root = BSTNode(key, value)
---> 16 self.root.insert(key, value)
17 elif key < self.root.key:
18 if self.root.left is None:
AttributeError: 'BSTNode' object has no attribute 'insert'
I would be grateful if you could provide any indicators to where I am going wrong with this, thank you.
Your "insert" node always operate on the root node of the tree. It should operate on whatever node it is inserting.
Maybe it is easier if you use a single class instead of a class for a Node and another for a Tree, that way, each node will have its own "insert" method that will do the right thing.
class BSTNode:
def __init__(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
def insert(self, key, value):
if key <= self.key:
if not self.left:
self.left = BSTNode(key, value)
else:
self.left.insert(key, value)
elif key > self.key:
if not self.right:
self.right = BSTNode(key, value)
else:
self.right.insert(key, value)