MUST BE IN PYTHON USING PYCHARM

starter code, can copy and paste into pycharm:

" " "

Find the shortest path between 2 nodes in a binary search tree. Modify function _find_path() which is called from find_path(). Follow instructions in _find_path() method to return list_path and steps. """ 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 class BinarySearchTree: def __init__(self): self.root = None self.size = 0 def length(self): return self.size def __len__(self): return self.size 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  1: nodeToRemove = self._get(key, self.root) if nodeToRemove: self.remove(nodeToRemove) self.size = self.size - 1 else: raise KeyError('Error, key not in tree') elif self.size == 1 and self.root.key == key: self.root = None self.size = self.size - 1 else: raise KeyError('Error, key not in tree') def __delitem__(self, key): self.delete(key) def spliceOut(self): if self.isLeaf(): if self.isLeftChild(): self.parent.leftChild = None else: self.parent.rightChild = None elif self.hasAnyChildren(): if self.hasLeftChild(): if self.isLeftChild(): self.parent.leftChild = self.leftChild else: self.parent.rightChild = self.leftChild self.leftChild.parent = self.parent else: if self.isLeftChild(): self.parent.leftChild = self.rightChild else: self.parent.rightChild = self.rightChild self.rightChild.parent = self.parent def findSuccessor(self): succ = None if self.hasRightChild(): succ = self.rightChild.findMin() else: if self.parent: if self.isLeftChild(): succ = self.parent else: self.parent.rightChild = None succ = self.parent.findSuccessor() self.parent.rightChild = self return succ def findMin(self): current = self while current.hasLeftChild(): current = current.leftChild return current def remove(self, currentNode): if currentNode.isLeaf(): # leaf if currentNode == currentNode.parent.leftChild: currentNode.parent.leftChild = None else: currentNode.parent.rightChild = None elif currentNode.hasBothChildren(): # interior succ = currentNode.findSuccessor() succ.spliceOut() currentNode.key = succ.key currentNode.payload = succ.payload else: # this node has one child if currentNode.hasLeftChild(): if currentNode.isLeftChild(): currentNode.leftChild.parent = currentNode.parent currentNode.parent.leftChild = currentNode.leftChild elif currentNode.isRightChild(): currentNode.leftChild.parent = currentNode.parent currentNode.parent.rightChild = currentNode.leftChild else: currentNode.replaceNodeData(currentNode.leftChild.key, currentNode.leftChild.payload, currentNode.leftChild.leftChild, currentNode.leftChild.rightChild) else: if currentNode.isLeftChild(): currentNode.rightChild.parent = currentNode.parent currentNode.parent.leftChild = currentNode.rightChild elif currentNode.isRightChild(): currentNode.rightChild.parent = currentNode.parent currentNode.parent.rightChild = currentNode.rightChild else: currentNode.replaceNodeData(currentNode.rightChild.key, currentNode.rightChild.payload, currentNode.rightChild.leftChild, currentNode.rightChild.rightChild) def main(): mytree = BinarySearchTree() mytree[4] = "red" mytree[8] = "yellow" mytree[6] = "blue" mytree[3] = "pew" """Use this for testing and debugging your code""" # print(mytree[6]) # print(mytree[2]) # path_list_steps = mytree.find_path(3, 8) # print(path_list_steps[0], path_list_steps[1]) # this prints list_path, steps if __name__ == "__main__": main()

Q2. (50 points) Find the shortest path between 2 nodes in a binary search tree (balancing isn't implemented in this one). Refer the comments in the question2.py to modify function_find path0 which is called from find path0. Follow instructions in find path0 method to return list path and steps. Q2. (50 points) Find the shortest path between 2 nodes in a binary search tree (balancing isn't implemented in this one). Refer the comments in the question2.py to modify function_find path0 which is called from find path0. Follow instructions in find path0 method to return list path and steps