Python.Python.Python

Problem: Delete node from BST Complete the function deleteNode() to take in a root node of a tree and a value of a node that is in the tree, and delete that node. This will follow the deletion process we discussed in class. I have already gotten you started with comments to guide you through it. I also provided you two functions that you will need, please do not modify or remove them since they're intended to help you solve this. However, feel free to write your own function/code for the deletion.

this is what was given:

class Node: def __init__(self, value): self.value = value self.left = None self.right = None def deleteNode(root, value): (node, parent) = findNodeAndParent(root, value) # case #1, if the target node doesn't have any children, remove it # if the target node is root, after deleting it, root will be None # else,if the target node is the left child or right child of it's parent, make # left or right child as none accordingly # case #2, if the node has only one child, # make the child of the target node a direct child of it's parent node # case #3, if the target node has two children # Find the successor and its parent using findSuccessorAndParent() # Replace target node value with successor node value # # Remove the successor by making its right child as # the left child of the successor's parent def findNodeAndParent(root, target, parent=None): # DO NOT DELETE OR MODIFY # this function searches for a node with `value` # and returns the node and its parent if root is None: return (None, None) if root.value == target: return (root, parent) if target < root.value: return findNodeAndParent(root.left, target, root) else: return findNodeAndParent(root.right, target, root) def findSuccessorAndParent(root): # DO NOT DELETE OR MODIFY if root.left and root.right is None: # the starting node is min and we don't have a way to access its parent return (root, None) #There are three cases to consider when looking for the successor:

#If the node has a right child, then the successor is the smallest key in the right subtree. #If the node has no right child and is the left child of its parent, then the parent is the successor. #If the node is the right child of its parent, and itself has no right child, then the successor to this node is the successor of its parent, excluding this node.