Maximum recursion depth exceeded when inserting in BST-CodePudding

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.

CodePudding user response：

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)