This is a Python 3.4 question. Modify the implementation of the binary search tr

Question

This is a Python 3.4 question.

Modify the implementation of the binary search tree to handle duplicate keys properly. This implies, if a key already exists in the tree, then the new payload should replace the old value. We do not add another node with the same key!

Code:

class BinarySearchTree:

def __init__(self):
self.root = None
self.size = 0

def length(self):
return self.size

def __len__(self):
return self.size

def __iter__(self):
return self.root.__iter__()

class TreeNode:
def __init__(self,key,val,left=None,right=None,
parent=None):
self.key = key
self.payload = val
self.leftChild = left
self.rightChild = right
self.parent = parent

def hasLeftChild(self):
return self.leftChild

def hasRightChild(self):
return self.rightChild
  
def isLeftChild(self):
return self.parent and
self.parent.leftChild == self

def isRightChild(self):
return self.parent and
self.parent.rightChild == self

def isRoot(self):
return not self.parent

def isLeaf(self):
return not (self.rightChild or self.leftChild)

def hasAnyChildren(self):
return self.rightChild or self.leftChild

def hasBothChildren(self):
return self.rightChild and self.leftChild
  
def replaceNodeData(self,key,value,lc,rc):
self.key = key
self.payload = value
self.leftChild = lc
self.rightChild = rc
if self.hasLeftChild():
self.leftChild.parent = self
if self.hasRightChild():
self.rightChild.parent = self

def put(self,key,val):
if self.root:
self._put(key,val,self.root)
else:
self.root = TreeNode(key,val)
self.size = self.size + 1
  
def _put(self,key,val,currentNode):
if key < currentNode.key:
if currentNode.hasLeftChild():
self._put(key,val,currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key,val,
parent=currentNode)
else:
if currentNode.hasRightChild():
self._put(key,val,currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key,val,
parent=currentNode)

Explanation / Answer

def _put(self,key,val,currentNode):
if key == currentNode.key:
currentNode.value = val
elif key < currentNode.key:
if currentNode.hasLeftChild():
self._put(key,val,currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key,val,parent=currentNode)
else:
if currentNode.hasRightChild():
self._put(key,val,currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key,val,parent=currentNode)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.