This was answered previously but was not correct. For Python 3.6.2 Modify the implementation of the binary search tree to handle duplicate keys properly (Listing_6_25a). 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!

Make sure to review the code carefully to determine where the new functionality needs to be added.

Show the printout of your results along with the code. Here's the code I have:

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 is not None def hasRightChild(self): return self.rightChild is not None def isLeftChild(self): return self.parent and self.parent.leftChild is self def isRightChild(self): return self.parent and self.parent.rightChild is self def isRoot(self): return not self.parent def isLeaf(self): return not (self.rightChild or self.leftChild) def hasAnyChildren(self): return not self.isLeaf() def hasBothChildren(self): return self.hasLeftChild() and self.hasRightChild() 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 findSuccessor(self): succ = None if self.isLeaf(): return None if self.hasRightChild(): return self.rightChild.findMin() if self.parent and self.isLeftChild(): return self.parent def findMin(self): if self.hasLeftChild(): return self.leftChild.findMin() else: return self def sliceOut(self): """ move node's child to its own position """ if self.parent and self.hasRightChild(): if self.isLeftChild(): self.parent.leftChild = self.rightChild else: self.parent.rightChild = self.rightChild def traverse(self): if self.hasLeftChild(): self.leftChild.traverse() print(self.payload) if self.hasRightChild(): self.rightChild.traverse() 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__() def put(self, key, val): if self.root: self._put(key, val, self.root) else: self.root = TreeNode(key, val) 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) def __setitem__(self, k, v): self.put(k, v) def get(self, key): if self.root: res = self._get(key, self.root) if res: return res.payload else: return None return None def _get(self, key, currentNode): if not currentNode: return None elif currentNode.key == key: return currentNode elif key < currentNode.key: return self._get(key, currentNode.leftChild) else: return self._get(key, currentNode.rightChild) def __getitem__(self, key): return self.get(key) def __contains__(self, key): if self._get(key, self.root): return True else: return False def delete(self, key): if self.size > 1: nodeToRemove = self._get(key, self.root) if nodeToRemove: self.remove(nodeToRemove) self.size -= 1 else: raise KeyError('Error, key is not in tree') elif self.size == 1 and self.root.key == key: self.root = None self.size = 0 else: raise KeyError('Error, key not in tree') def __delitem__(self, key): self.delete(key) def remove(self, currentNode): if currentNode.isLeaf(): if currentNode.isLeftChild(): currentNode.parent.leftChild = None else: currentNode.parent.rightChild = None elif currentNode.hasBothChildren(): succ = currentNode.findSuccessor() succ.sliceOut() currentNode.key = succ.key currentNode.payload = succ.payload elif currentNode.hasLeftChild(): if currentNode.isLeftChild():

currentNode.parent.leftChild = currentNode.leftChild else: currentNode.parent.rightChild = currentNode.leftChild else: if currentNode.isLeftChild(): currentNode.parent.rightChild = currentNode.rightChild else: currentNode.parent.rightChild = currentNode.leftChild def main(): mytree = BinarySearchTree() mytree[3]="red" mytree[4]="blue" mytree[6]="yellow" mytree[2]="at"

print(mytree[6]) print(mytree[2]) main()

Need to code to be reviewed to ensure outputs properly & code to be well commented.