Asking how to insert a new node to BST? Python

Question

I am doing my practice, and the practice request create DSATreeNode and DSABinarySearchTree classes. The DSATreeNode is working fine, but when I use the function of insertRec. The insert function will call the insertRec that store the node in the right place. The problem comes is it is not storing and there is nothing in new node. Also the self._root is None, never insert anything into it.

Here's my code

class DSATreeNode:
    def __init__(self, inKey, inValue):
        self._key = inKey
        self._value = inValue
        self._left = self._right = None

class DSABinarySearchTree:
    def __init__(self):
        self._root = None

    def find(self, key):
        return self._findRec(key, self._root)
    
    def _findRec(self, key, cur):
        value = None
        if cur == None: # Base case: not found
            raise Exception("Key " + key + " not found")
        elif key == cur._key: # Base case: found
            value = cur._value
        elif key < cur._key: # Go left (recursive)
            value = self._findRec(key, cur._left)
        else: # Go right(recursive)
            value = self._findRec(key, cur._right)
        
        return value

    def insert(self, inKey, inValue):
        return self.insertRec(inKey, inValue, self._root)

    def insertRec(self, key, value, curNode):
        createNode = DSATreeNode(key, value)
        if curNode == None:
            curNode = createNode
        elif key < curNode._key:
            curNode._left = self.insertRec(key, value, curNode._left)
        else:
            curNode._right = self.insertRec(key, value, curNode._right)

    def getRoot(self):
        return self._root._key, self._root._value

Answer 1

A few issues:

• _insertRec does not return a node. It should have return curNode as its last statement.

• There is no code that assigns a node to self._root. The insert method should assign like this: self._root = self.insertRec(inKey, inValue, self._root).

• The error message generated in _findRec assumes that key is a string, but if it isn't, then it will fail. Better do raise Exception("Key " + str(key) + " not found") or raise Exception(f"Key {key} not found")

• Not blocking, but _insertRec should not create a node when it still is going to make a recursive call. So move that first line into the first if block:

      if curNode == None:
          curNode = DSATreeNode(key, value)