Why is my insert() function not inserting a new root node?

April 10, 2022

I’m trying to make a recursive insert function for my binary search tree class, but when I test it, it keeps saying that the root is None after I have tried inserting a new node.
I have a class DSATreeNode that takes arguments for the node’s key and value, and have defined the str() function forDSATreeNode too.

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

    def insert(self, key, value): 
        return self._insertRec(key, value, self._root)

    def _insertRec(self, key, value, curNode):
        if curNode != None:
            if key < curNode._key:
                if curNode.getLeft() == None:
                    curNode.setLeft(DSATreeNode(key, value))
                else:
                    self._insertRec(key, value, curNode.getLeft())
            elif key > curNode._key:
                if curNode.getRight() == None:
                    curNode.setRight(DSATreeNode(key, value))
                else:
                    self._insertRec(key, value, curNode.getRight())
        else:
            curNode = DSATreeNode(key, value)


if __name__ == "__main__": 
    print("Testing tree creation and traversal")
    myTree = DSABinarySearchTree()
    myTree.insert(1, "one")
    print("root: ", str(myTree._root))

>Solution :

def _insertRec(self, key, value, curNode):
    if curNode != None:
        ...
    else:
        curNode = DSATreeNode(key, value)

This is your problem. When you assign to curNode, that does not update self._root. It rebinds the name curNode to a new value (which is then lost when the function exits.)

It seems like you’re expecting curNode to be a pointer back to self._root, which it is not.