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))
CodePudding user response:
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.