Why does this BST implementation not work?

Question

As part of a project I have to implement a BST with the purpose of sorting through a big dictionary of keys and values. However, I'm having some problems with my code. Specifically, I get an error message because I've exceeded the maximum recursion limit.

Here is the code:

@dataclass
class Node:
    key: Any = None
    value: Any = None
    left: Any = None
    right: Any = None

def put(self, key, value):
    new_node = Node(key, value)
    if new_node.value < self.value:
        if self.left is None:
            self.left = Node(key, value, None, None)
        else:
            self.put(key, value)
    elif new_node.value > self.value:
        if self.right is None:
            self.right = Node(key, value, None, None)
        else:
            self.put(key, value)

I understand I've created an infinite recursive function, but I dont understand why. Looking at it, it seems to me that it should not be infinite. Can someone tell me what I've done wrong?

Answer 1

As far as I can see, your recursive calls self.put(key, value) are identical (same arguments) to the initial call, which causes the infinite loop; think about how you want your algorithm to behave (simulating the process on a diagram helps).

For future reference, here's the fixed code (only fixes the issue mentioned in the questions; there's still room for improvements).

@dataclass
class Node:
    key: Any = None
    value: Any = None
    left: Any = None
    right: Any = None

def put(self, key, value):
    new_node = Node(key, value)
    if new_node.value < self.value:
        if self.left is None:
            self.left = Node(key, value, None, None)
        else:
            self.left.put(key, value)
    elif new_node.value > self.value:
        if self.right is None:
            self.right = Node(key, value, None, None)
        else:
            self.right.put(key, value)